线段树入门总结

线段树的入门级 总结

      线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。       对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。       使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

----来自百度百科

【以下以 求区间最大值为例】 先看声明:

1 #include <stdio.h>
2 #include <math.h>
3 const int MAXNODE = 2097152;
4 const int MAX = 1000003;
5 struct NODE{
6     int value;        // 结点对应区间的权值
7     int left,right;   // 区间 [left,right]
8 }node[MAXNODE];
9 int father[MAX];     // 每个点(当区间长度为0时,对应一个点)对应的结构体数组下标

【创建线段树(初始化)】:

       由于线段树是用二叉树结构储存的,而且是近乎完全二叉树的,所以在这里我使用了数组来代替链表上图中区间上面的红色数字表示了结构体数组中对应的下标。

在完全二叉树中假如一个结点的序号(数组下标)为 I ,那么 (二叉树基本关系)

I 的父亲为 I/2,

I 的另一个兄弟为 I/2*2 或 I/2*2+1

I 的两个孩子为 I*2 (左)   I*2+1(右)

有了这样的关系之后,我们便能很方便的写出创建线段树的代码了。

 1 void BuildTree(int i,int left,int right){ // 为区间[left,right]建立一个以i为祖先的线段树,i为数组下标,我称作结点序号
 2     node[i].left = left;    // 写入第i个结点中的 左区间
 3     node[i].right = right;    // 写入第i个结点中的 右区间
 4     node[i].value = 0;         // 每个区间初始化为 0
 5     if (left == right){    // 当区间长度为 0 时,结束递归
 6         father[left] = i; // 能知道某个点对应的序号,为了更新的时候从下往上一直到顶
 7         return;
 8     }
 9     // 该结点往 左孩子的方向 继续建立线段树,线段的划分是二分思想,如果写过二分查找的话这里很容易接受
10     // 这里将 区间[left,right] 一分为二了
11     BuildTree(i<<1, left, (int)floor( (right+left) / 2.0));
12     // 该结点往 右孩子的方向 继续建立线段树
13     BuildTree((i<<1) + 1, (int)floor( (right+left) / 2.0) + 1, right);
14 }

【单点更新线段树】:

       由于我事先用 father[ ] 数组保存过 每单个结点 对应的下标了,因此我只需要知道第几个点,就能知道这个点在结构体中的位置(即下标)了,这样的话,根据之前已知的基本关系,就只需要直接一路更新上去即可。

1 void UpdataTree(int ri){ // 从下往上更新(注:这个点本身已经在函数外更新过了)
2 
3     if (ri == 1)return;    // 向上已经找到了祖先(整个线段树的祖先结点 对应的下标为1)
4     int fi = ri / 2;         // ri 的父结点
5     int a = node[fi<<1].value; // 该父结点的两个孩子结点(左)
6     int b = node[(fi<<1)+1].value; // 右
7     node[fi].value = (a > b)?(a):(b);    // 更新这个父结点(从两个孩子结点中挑个大的)
8     UpdataTree(ri/2);        // 递归更新,由父结点往上找
9 }

【查询区间最大值】:        将一段区间按照建立的线段树从上往下一直拆开,直到存在有完全重合的区间停止。对照图例建立的树,假如查询区间为 [2,5]

红色的区间为完全重合的区间,因为在这个具体问题中我们只需要比较这 三个区间的值 找出 最大值 即可。

 1 int Max = -1<<20;
 2 void Query(int i,int l,int r){ // i为区间的序号(对应的区间是最大范围的那个区间,也是第一个图最顶端的区间,一般初始是 1 啦)
 3     if (node[i].left == l && node[i].right == r){ // 找到了一个完全重合的区间
 4         Max = (Max < node[i].value)?node[i].value:(Max);
 5         return ;
 6     }
 7     i = i << 1; // get the left child of the tree node
 8     if (l <= node[i].right){ // 左区间有涉及
 9         if (r <= node[i].right) // 全包含于左区间,则查询区间形态不变
10             Query(i, l, r);
11         else // 半包含于左区间,则查询区间拆分,左端点不变,右端点变为左孩子的右区间端点
12             Query(i, l, node[i].right);
13     }
14     i += 1; // right child of the tree
15     if (r >= node[i].left){ // 右区间有涉及
16         if (l >= node[i].left) // 全包含于右区间,则查询区间形态不变
17             Query(i, l, r);
18         else // 半包含于左区间,则查询区间拆分,与上同理
19             Query(i, node[i].left, r);
20     }
21 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

1890
来自专栏青玉伏案

算法与数据结构(十四) 堆排序 (Swift 3.0版)

上篇博客主要讲了冒泡排序、插入排序、希尔排序以及选择排序。本篇博客就来讲一下堆排序(Heap Sort)。看到堆排序这个名字我们就应该知道这种排序方式的特点,就...

24810
来自专栏用户2442861的专栏

STL关联容器-红黑树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

963
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

2488
来自专栏Android知识点总结

03--图解数据结构之双链表实现容器

1065
来自专栏杨熹的专栏

【LEETCODE】模拟面试-46. Permutations

notice: if ( curList.contains(arr[i]) ){ continue; ...

36912
来自专栏蜉蝣禅修之道

LeetCode之Binary Tree Maximum Path Sum

1174
来自专栏数据结构与算法

P3379 【模板】最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数...

4326
来自专栏数据结构与算法

洛谷 P3386 【模板】二分图匹配 Dinic版

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

3309
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

1262

扫码关注云+社区

领取腾讯云代金券