线段树详解

傷城~ 2022-08-05 13:13 174阅读 0赞

# 一：线段树基本概念 #

**1：概述**

**线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!**

**性质：父亲的区间是\[a,b\],(c=(a+b)/2)左儿子的区间是\[a,c\]，右儿子的区间是\[c+1,b\]，线段树需要的空间为数组大小的四倍**

![8039326][]

**2：基本操作（demo用的是查询区间最小值）**

**线段树的主要操作有：**

**(1)：线段树的构造 void build(int node, int begin, int end);**

**主要思想是递归构造，如果当前节点记录的区间只有一个值，则直接赋值，否则递归构造左右子树，最后回溯的时候给当前节点赋值**

1.  \#include <iostream>  
2.  **using** **namespace** std;  
3.    
4.  **const** **int** maxind = 256;  
5.  **int** segTree\[maxind \* 4 + 10\];  
6.  **int** array\[maxind\];   
7.  /\* 构造函数，得到线段树 \*/  
8.  **void** build(**int** node, **int** begin, **int** end)    
9.  \{    
10.     **if** (begin == end)    
11.         segTree\[node\] = array\[begin\]; /\* 只有一个元素,节点记录该单元素 \*/  
12.     **else**    
13.     \{     
14.         /\* 递归构造左右子树 \*/   
15.         build(2\*node, begin, (begin+end)/2);    
16.         build(2\*node+1, (begin+end)/2+1, end);   
17.            
18.         /\* 回溯时得到当前node节点的线段信息 \*/    
19.         **if** (segTree\[2 \* node\] <= segTree\[2 \* node + 1\])    
20.             segTree\[node\] = segTree\[2 \* node\];    
21.         **else**    
22.             segTree\[node\] = segTree\[2 \* node + 1\];    
23.     \}    
24. \}  
25.   
26. **int** main()  
27. \{  
28.     array\[0\] = 1, array\[1\] = 2,array\[2\] = 2, array\[3\] = 4, array\[4\] = 1, array\[5\] = 3;  
29.     build(1, 0, 5);  
30.     **for**(**int** i = 1; i<=20; ++i)  
31.      cout<< "seg"<< i << "=" <<segTree\[i\] <<endl;  
32.     **return** 0;  
33. \}

此build构造成的树如图： ![1349329624_4255.jpg][]

**(2)：区间查询int query(int node, int begin, int end, int left, int right);**

**（其中node为当前查询节点，begin,end为当前节点存储的区间，left,right为此次query所要查询的区间）**

**主要思想是把所要查询的区间\[a,b\]划分为线段树上的节点，然后将这些节点代表的区间合并起来得到所需信息**

**比如前面一个图中所示的树，如果询问区间是\[0,2\]，或者询问的区间是\[3,3\]，不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答，比如\[0,3\]，就没有哪一个节点记录了这个区间的最小值。当然，解决方法也不难找到：把\[0,2\]和\[3,3\]两个区间（它们在整数意义上是相连的两个区间）的最小值“合并”起来，也就是求这两个最小值的最小值，就能求出\[0,3\]范围的最小值。同理，对于其他询问的区间，也都可以找到若干个相连的区间，合并后可以得到询问的区间。**

1.  **int** query(**int** node, **int** begin, **int** end, **int** left, **int** right)    
2.  \{   
3.      **int** p1, p2;    
4.      
5.      /\*  查询区间和要求的区间没有交集  \*/  
6.      **if** (left > end || right < begin)    
7.          **return** -1;    
8.      
9.      /\*  if the current interval is included in  \*/    
10.     /\*  the query interval return segTree\[node\]  \*/  
11.     **if** (begin >= left && end <= right)    
12.         **return** segTree\[node\];    
13.     
14.     /\*  compute the minimum position in the  \*/  
15.     /\*  left and right part of the interval  \*/   
16.     p1 = query(2 \* node, begin, (begin + end) / 2, left, right);   
17.     p2 = query(2 \* node + 1, (begin + end) / 2 + 1, end, left, right);    
18.     
19.     /\*  return the expect value  \*/   
20.     **if** (p1 == -1)    
21.         **return** p2;    
22.     **if** (p2 == -1)    
23.         **return** p1;    
24.     **if** (p1 <= p2)    
25.         **return**  p1;    
26.     **return**  p2;      
27. \}

**可见，这样的过程一定选出了尽量少的区间，它们相连后正好涵盖了整个\[left,right\]，没有重复也没有遗漏。同时，考虑到线段树上每层的节点最多会被选取2个，一共选取的节点数也是O(log n)的，因此查询的时间复杂度也是O(log n)。**

**线段树并不适合所有区间查询情况，它的使用条件是“相邻的区间的信息可以被合并成两个区间的并区间的信息”。即问题是可以被分解解决的。**

**(3)：区间或节点的更新 及 线段树的动态维护update （这是线段树核心价值所在，节点中的标记域可以解决N多种问题）**

**动态维护需要用到标记域，延迟标记等。**

**a:单节点更新**

1.  **void** Updata(**int** node, **int** begin, **int** end, **int** ind, **int** add)/\*单节点更新\*/    
2.  \{    
3.      
4.      **if**( begin == end )    
5.      \{    
6.          segTree\[node\] += add;    
7.          **return** ;    
8.      \}    
9.      **int** m = ( left + right ) >> 1;    
10.     **if**(ind <= m)    
11.         Updata(node \* 2,left, m, ind, add);    
12.     **else**    
13.         Updata(node \* 2 + 1, m + 1, right, ind, add);    
14.     /\*回溯更新父节点\*/    
15.     segTree\[node\] = min(segTree\[node \* 2\], segTree\[node \* 2 + 1\]);     
16.          
17. \}

**b：区间更新（线段树中最有用的）**

**需要用到延迟标记，每个结点新增加一个标记，记录这个结点是否被进行了某种修改操作(这种修改操作会影响其子结点)。对于任意区间的修改，我们先按照查询的方式将其划分成线段树中的结点，然后修改这些结点的信息，并给这些结点标上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个结点p，并且决定考虑其子结点，那么我们就要看看结点p有没有标记，如果有，就要按照标记修改其子结点的信息，并且给子结点都标上相同的标记，同时消掉p的标记。（优点在于，不用将区间内的所有值都暴力更新，大大提高效率，因此区间更新是最优用的操作）**

**void Change来自[dongxicheng.org][]**

1.  **void** Change(node \*p, **int** a, **int** b) /\* 当前考察结点为p，修改区间为(a,b\]\*/  
2.     
3.  \{  
4.     
5.    **if** (a <= p->Left && p->Right <= b)  
6.     
7.    /\* 如果当前结点的区间包含在修改区间内\*/  
8.     
9.    \{  
10.    
11.      ...... /\* 修改当前结点的信息，并标上标记\*/  
12.    
13.      **return**;  
14.    
15.   \}  
16.    
17.   Push\_Down(p); /\* 把当前结点的标记向下传递\*/  
18.    
19.   **int** mid = (p->Left + p->Right) / 2; /\* 计算左右子结点的分隔点 
20.   
21.   if (a < mid) Change(p->Lch, a, b); /\* 和左孩子有交集，考察左子结点\*/  
22.    
23.   **if** (b > mid) Change(p->Rch, a, b); /\* 和右孩子有交集，考察右子结点\*/  
24.    
25.   Update(p); /\* 维护当前结点的信息（因为其子结点的信息可能有更改）\*/  
26.    
27. \}

**3:主要应用**

**(1)：区间最值查询问题 （见模板1）**

**(2)：连续区间修改或者单节点更新的动态查询问题 （见模板2）**

**(3)：多维空间的动态查询 （见模板3）**

# **二：典型模板** #

**模板1：**

**RMQ，查询区间最值下标---min**

1.  \#include<iostream>    
2.    
3.  **using** **namespace** std;    
4.      
5.  \#define MAXN 100    
6.  \#define MAXIND 256 //线段树节点个数    
7.      
8.  //构建线段树,目的:得到M数组.    
9.  **void** build(**int** node, **int** b, **int** e, **int** M\[\], **int** A\[\])    
10. \{    
11.     **if** (b == e)    
12.         M\[node\] = b; //只有一个元素,只有一个下标    
13.     **else**    
14.     \{     
15.         build(2 \* node, b, (b + e) / 2, M, A);    
16.         build(2 \* node + 1, (b + e) / 2 + 1, e, M, A);    
17.   
18.         **if** (A\[M\[2 \* node\]\] <= A\[M\[2 \* node + 1\]\])    
19.             M\[node\] = M\[2 \* node\];    
20.         **else**    
21.             M\[node\] = M\[2 \* node + 1\];    
22.     \}    
23. \}    
24.     
25. //找出区间 \[i, j\] 上的最小值的索引    
26. **int** query(**int** node, **int** b, **int** e, **int** M\[\], **int** A\[\], **int** i, **int** j)    
27. \{    
28.     **int** p1, p2;    
29.     
30.     //查询区间和要求的区间没有交集    
31.     **if** (i > e || j < b)    
32.         **return** -1;    
33.   
34.     **if** (b >= i && e <= j)    
35.         **return** M\[node\];    
36.    
37.     p1 = query(2 \* node, b, (b + e) / 2, M, A, i, j);    
38.     p2 = query(2 \* node + 1, (b + e) / 2 + 1, e, M, A, i, j);    
39.     
40.     //return the position where the overall    
41.     //minimum is    
42.     **if** (p1 == -1)    
43.         **return** M\[node\] = p2;    
44.     **if** (p2 == -1)    
45.         **return** M\[node\] = p1;    
46.     **if** (A\[p1\] <= A\[p2\])    
47.         **return** M\[node\] = p1;    
48.     **return** M\[node\] = p2;    
49.     
50. \}    
51.     
52.     
53. **int** main()    
54. \{    
55.     **int** M\[MAXIND\]; //下标1起才有意义,否则不是二叉树,保存下标编号节点对应区间最小值的下标.    
56.     memset(M,-1,**sizeof**(M));    
57.     **int** a\[\]=\{3,4,5,7,2,1,0,3,4,5\};    
58.     build(1, 0, **sizeof**(a)/**sizeof**(a\[0\])-1, M, a);    
59.     cout<<query(1, 0, **sizeof**(a)/**sizeof**(a\[0\])-1, M, a, 0, 5)<<endl;    
60.     **return** 0;    
61. \}

**模板2：**

**连续区间修改或者单节点更新的动态查询问题 （此模板查询区间和）**

1.  \#include <cstdio>    
2.  \#include <algorithm>    
3.  **using** **namespace** std;    
4.       
5.  \#define lson l , m , rt << 1    
6.  \#define rson m + 1 , r , rt << 1 | 1   
7.  \#define root 1 , N , 1   
8.  \#define LL long long    
9.  **const** **int** maxn = 111111;    
10. LL add\[maxn<<2\];    
11. LL sum\[maxn<<2\];    
12. **void** PushUp(**int** rt) \{    
13.     sum\[rt\] = sum\[rt<<1\] + sum\[rt<<1|1\];    
14. \}    
15. **void** PushDown(**int** rt,**int** m) \{    
16.     **if** (add\[rt\]) \{    
17.         add\[rt<<1\] += add\[rt\];    
18.         add\[rt<<1|1\] += add\[rt\];    
19.         sum\[rt<<1\] += add\[rt\] \* (m - (m >> 1));    
20.         sum\[rt<<1|1\] += add\[rt\] \* (m >> 1);    
21.         add\[rt\] = 0;    
22.     \}    
23. \}    
24. **void** build(**int** l,**int** r,**int** rt) \{    
25.     add\[rt\] = 0;    
26.     **if** (l == r) \{    
27.         scanf("%lld",&sum\[rt\]);    
28.         **return** ;    
29.     \}    
30.     **int** m = (l + r) >> 1;    
31.     build(lson);    
32.     build(rson);    
33.     PushUp(rt);    
34. \}    
35. **void** update(**int** L,**int** R,**int** c,**int** l,**int** r,**int** rt) \{    
36.     **if** (L <= l && r <= R) \{    
37.         add\[rt\] += c;    
38.         sum\[rt\] += (LL)c \* (r - l + 1);    
39.         **return** ;    
40.     \}    
41.     PushDown(rt , r - l + 1);    
42.     **int** m = (l + r) >> 1;    
43.     **if** (L <= m) update(L , R , c , lson);    
44.     **if** (m < R) update(L , R , c , rson);    
45.     PushUp(rt);    
46. \}    
47. LL query(**int** L,**int** R,**int** l,**int** r,**int** rt) \{    
48.     **if** (L <= l && r <= R) \{    
49.         **return** sum\[rt\];    
50.     \}    
51.     PushDown(rt , r - l + 1);    
52.     **int** m = (l + r) >> 1;    
53.     LL ret = 0;    
54.     **if** (L <= m) ret += query(L , R , lson);    
55.     **if** (m < R) ret += query(L , R , rson);    
56.     **return** ret;    
57. \}    
58. **int** main() \{    
59.     **int** N , Q;    
60.     scanf("%d%d",&N,&Q);    
61.     build(root);    
62.     **while** (Q --) \{    
63.         **char** op\[2\];    
64.         **int** a , b , c;    
65.         scanf("%s",op);    
66.         **if** (op\[0\] == 'Q') \{    
67.             scanf("%d%d",&a,&b);    
68.             printf("%lld\\n",query(a , b ,root));    
69.         \} **else** \{    
70.             scanf("%d%d%d",&a,&b,&c);    
71.             update(a , b , c , root);    
72.         \}    
73.     \}    
74.     **return** 0;    
75. \}

转自：[/images/20220805/868fea2d1367403dad9db5e4e2277c61.png][8039326]

[8039326]: /images/20220805/868fea2d1367403dad9db5e4e2277c61.png
[1349329624_4255.jpg]: https://img-my.csdn.net/uploads/201210/04/1349329624_4255.jpg
[dongxicheng.org]: http://blog.csdn.net/metalseed/article/details/dongxicheng.org