java数据结构与算法总结(二十一)--线段树

末蓝、 2023-02-14 13:10 2阅读 0赞

一：为什么需要线段树？

>   
> 题目一：  
> 10000个正整数，编号1到10000，用A\[1\],A\[2\],A\[10000\]表示。  
> 修改：无  
> 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.

方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做\[L..R\],问题就是对A\[L..R\]进行求和。  
这样求和，对于每个询问，需要将(R-L+1)个数相加。

方法二：更快的方法是求前缀和,令 S\[0\]=0, S\[k\]=A\[1..k\] ，那么，A\[L..R\]的和就等于S\[R\]-S\[L-1\]，  
这样，对于每个询问，就只需要做一次减法，大大提高效率。

>   
> 题目二：  
> 10000个正整数，编号从1到10000，用A\[1\],A\[2\],A\[10000\]表示。  
> 修改：1.将第L个数增加C （1 <= L <= 10000）  
> 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.

再使用方法二的话，假如A\[L\]+=C之后，S\[L\],S\[L+1\],,S\[R\]都需要增加C,全部都要修改，见下表。

<table style="width:591px;"> 
 <tbody> 
  <tr> 
   <td style="vertical-align:middle;width:54pt;">&nbsp;</td> 
   <td style="border-color:#000000 #dddddd #dddddd #000000;text-align:left;vertical-align:middle;width:296px;"><span style="color:#4f4f4f;">方法一</span></td> 
   <td style="border-color:#000000 #dddddd #dddddd;text-align:left;vertical-align:middle;width:221px;"><span style="color:#4f4f4f;">方法二</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#dddddd #dddddd #dddddd #000000;text-align:left;vertical-align:middle;width:54pt;"><span style="color:#4f4f4f;">A[L]+=C</span></td> 
   <td style="border-color:#dddddd;text-align:left;vertical-align:middle;width:296px;"><span style="color:#4f4f4f;">修改1个元素</span></td> 
   <td style="border-color:#dddddd #000000 #dddddd #dddddd;text-align:left;vertical-align:middle;width:221px;"><span style="color:#4f4f4f;">修改R-L+1个元素</span></td> 
  </tr> 
  <tr> 
   <td style="border-color:#dddddd #dddddd #000000 #000000;text-align:left;vertical-align:middle;width:54pt;"><span style="color:#4f4f4f;">求和A[L..R]</span></td> 
   <td style="border-color:#dddddd #dddddd #000000;text-align:left;vertical-align:middle;width:296px;"><span style="color:#4f4f4f;">计算R-L+1个元素之和</span></td> 
   <td style="border-color:#dddddd #000000 #000000 #dddddd;text-align:left;vertical-align:middle;width:221px;"><span style="color:#4f4f4f;">计算两个元素之差</span></td> 
  </tr> 
 </tbody> 
</table>

从上表可以看出，方法一修改快，求和慢。 方法二求和快，修改慢。  
那有没有一种结构，修改和求和都比较快呢？答案当然是线段树。

二：线段树的点修改

上面的问题二就是典型的线段树点修改。  
线段树先将区间\[1..10000\]分成不超过4\*10000个子区间，对于每个子区间，记录一段连续数字的和。  
之后，任意给定区间\[L,R\]，线段树在上述子区间中选择约2\*log2(R-L+1)个拼成区间\[L,R\]。  
如果A\[L\]+=C ，线段树的子区间中，约有log2(10000)个包含了L，所以需要修改log2(10000)个。

于是，使用线段树的话，  
A\[L\]+=C 需要修改log2(10000) 个元素  
求和A\[L...R\]需要修改2\*log2(R-L+1) <= 2 \* log2(10000) 个元素。  
log2(10000) < 14 所以相对来说线段树的修改和求和都比较快。

**问题一：开始的子区间是怎么分的？**  
首先是讲原始子区间的分解，假定给定区间\[L,R\]，只要L < R ，线段树就会把它继续分裂成两个区间。  
首先计算 M = (L+R)/2，左子区间为\[L,M\]，右子区间为\[M+1,R\]，然后如果子区间不满足条件就递归分解。  
以区间\[1..13\]的分解为例，分解结果见下图：

![SouthEast][]

**问题二：给定区间【L,R】，如何分解成上述给定的区间？**  
对于给定区间\[2,12\]要如何分解成上述区间呢？

**分解方法一：自下而上合并——利于理解**  
先考虑树的最下层，将所有在区间\[2,12\]内的点选中，然后，若相邻的点的直接父节点是同一个，那么就用这个父节点代替这两个节点（父节点在上一层）。这样操作之后，本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树，那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树，那么这个节点会被剩下。中间的所有节点都被父节点取代。对最下层处理完之后，考虑它的上一层，继续进行同样的处理。

下图为n=13的线段树，区间\[2,12\]，按照上面的叙述进行操作的过程图：

![SouthEast 1][]

![SouthEast 2][]

![SouthEast 3][]

![SouthEast 4][]

由图可以看出：在n=13的线段树中，\[2,12\]=\[2\] + \[3,4\] + \[5,7\] + \[8,10\] + \[11,12\] 。

**分解方法二：自上而下分解——利于计算**

![SouthEast 5][]

首先对于区间\[1,13\]，计算(1+13)/2 = 7，于是将区间\[2,12\]“切割”成了\[2,7\]和\[8,12\]。

![SouthEast 6][]

其中\[2,7\]处于节点\[1,7\]的位置，\[2,7\] < \[1,7\] 所以继续分解，计算(1+7)/2 = 4, 于是将\[2,7\] 切割成\[2,4\]和\[5,7\]。

![SouthEast 7][]

\[5,7\]处于节点\[5,7\]的位置，所以不用继续分解，\[2,4\]处于区间\[1,4\]的位置，所以继续分解成\[2\]和\[3,4\]。

![SouthEast 8][]

最后【2】 < 【1,2】，所以计算(1+2)/2=1 ，将【2】用1切割，左侧为空，右侧为【2】

![SouthEast 9][]

当然程序是递归计算的，不是一层一层计算的，上图只表示计算方法，不代表计算顺序。

**问题三：如何进行区间统计？**  
假设这13个数为1,2,3,4,1,2,3,4,1,2,3,4,1. 在区间之后标上该区间的数字之和：

![SouthEast 10][]

如果要计算\[2,12\]的和，按照之前的算法：  
\[2,12\]=\[2\] + \[3,4\] + \[5,7\] + \[8,10\] + \[11,12\]  
  29  = 2 + 7 + 6 + 7 + 7  
计算5个数的和就可以算出\[2,12\]的值。

**问题四：如何进行点修改？**  
假设把A\[6\]+=7 ,看看哪些区间需要修改？\[6\],\[5,6\],\[5,7\],\[1,7\],\[1,13\]这些区间全部都需要+7.其余所有区间都不用动。  
于是，这颗线段树中，点修改最多修改5个线段树元素（每层一个）。  
下图中，修改后的元素用蓝色表示。

![SouthEast 11][]

**问题五：存储结构是怎样的？**

线段树是一种二叉树，当然可以像一般的树那样写成结构体，指针什么的。  
但是它的优点是，它也可以用数组来实现树形结构，可以大大简化代码。  
数组形式适合在编程竞赛中使用，在已经知道线段树的最大规模的情况下，直接开足够空间的数组，然后在上面建立线段树。  
简单的记法： 足够的空间 = 数组大小n的四倍。   
实际上足够的空间 =  （n向上扩充到最近的2的某个次方）的两倍。  
举例子：假设数组长度为5，就需要5先扩充成8，8\*2=16.线段树需要16个元素。如果数组元素为8，那么也需要16个元素。  
所以线段树需要的空间是n的两倍到四倍之间的某个数，一般就开4\*n的空间就好，如果空间不够，可以自己算好最大值来省点空间。

怎么用数组来表示一颗二叉树呢？假设某个节点的编号为v,那么它的左子节点编号为2\*v，右子节点编号为2\*v+1。  
然后规定根节点为1.这样一颗二叉树就构造完成了。通常2\*v在代码中写成 v<<1 。 2\*v+1写成 v<<1|1 。

**问题六：代码中如何实现？**  
(0)定义：

#define maxn 100007  //元素总个数  
    int Sum[maxn<<2];//Sum求和，开四倍空间
    int A[maxn],n;//存原数组下标[1，n]

(1)建树：

//PushUp函数更新节点信息，这里是求和
    void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  
    //Build函数建立线段树
    void Build(int l,int r,int rt){ //[l,r]表示当前节点区间，rt表示当前节点的实际存储位置 
        if(l==r) {//若到达叶节点 
            Sum[rt]=A[l];//存储A数组的值
            return;  
        }  
        int m=(l+r)>>1;  
       //左右递归
        Build(l,m,rt<<1);  
        Build(m+1,r,rt<<1|1);  
        //更新信息
        PushUp(rt);  
    }

(2)点修改：

假设A\[L\]+=C:

void Update(int L,int C,int l,int r,int rt){//[l,r]表示当前区间，rt是当前节点编号//l,r表示当前节点区间，rt表示当前节点编号  
        if(l==r){//到达叶节点，修改叶节点的值
            Sum[rt]+=C;  
            return;  
        }  
        int m=(l+r)>>1;  
       //根据条件判断往左子树调用还是往右
        if(L <= m) Update(L,C,l,m,rt<<1);  
        else       Update(L,C,m+1,r,rt<<1|1);  
        PushUp(rt);//子节点的信息更新了，所以本节点也要更新信息
    }

点修改其实可以写的更简单，只需要把一路经过的Sum都+=C就行了，不过上面的代码更加规范，在题目更加复杂的时候，按照格式写更不容易错。

**(3)区间查询（本题为求和）：**

询问A\[L..R\]的和  
注意到，整个函数的递归过程中，L,R是不变的。  
首先如果当前区间\[l,r\]在\[L,R\]内部，就直接累加答案  
如果左子区间与\[L,R\]有重叠，就递归左子树，右子树同理。

int Query(int L,int R,int l,int r,int rt){//[L,R]表示操作区间，[l,r]表示当前区间，rt:当前节点编号
        if(L <= l && r <= R){  
           //在区间内直接返回
            return Sum[rt];  
        }  
        int m=(l+r)>>1;  
        //左子区间:[l,m] 右子区间：[m+1,r]  求和区间:[L,R]
       //累加答案
        int ANS=0;  
        if(L <= m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠，递归
        if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1); //右子区间与[L,R]有重叠，递归
        return ANS;  
    }

最后：

线段树还有更多的用法，比如区间修改，扫描线，非递归写法等，详见这篇文章：[ 线段树详解][Link 1]

————————————————  
版权声明：本文为CSDN博主「岩之痕」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/zearot/article/details/52280189

[SouthEast]: https://img-blog.csdn.net/20160822213352759?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20150909172342229?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20150909172350036?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 3]: https://img-blog.csdn.net/20150909172354161?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20150909172357585?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 5]: https://img-blog.csdn.net/20160822220027137?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 6]: https://img-blog.csdn.net/20160822220059591?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 7]: https://img-blog.csdn.net/20160822220118296?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 8]: https://img-blog.csdn.net/20160822220140874?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 9]: https://img-blog.csdn.net/20160822220311424?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 10]: https://img-blog.csdn.net/20160822221733583?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 11]: https://img-blog.csdn.net/20160822222554087?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[Link 1]: https://blog.csdn.net/zearot/article/details/48299459