作者
王乙堃
来源
程序员小灰
线段树是一个复杂的数据结构，比较难理解，也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候，我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。
这篇文章比较长，建议大家耐心阅读，好好消化吸收哦~~
前置内容
学习线段树前，你需要掌握二叉搜索树，我只补充一个内容，就是关于二叉搜索树如何编号。
二叉搜索树的根节点编号为1，对于每个节点，假如其编号为N，它的左儿子编号为2N，右儿子编号为2N+1。因此，整个二叉搜索树的编号如下：
上图当中，结点上方的数字是结点的编号，后续为了简单，把编号写在结点内不。
有读者可能要问了，为什么3的儿子是6和7，而不是4和5呢？这是因为虽然节点4和节点5不存在，但是仍然应该为他们保留4和5这2个编号，你可以把这棵树看成这样：
线段树的概念
线段树，英文名称是SegmentTree，其本质也是一个二叉搜索树，区别在于线段树的每一个节点记录的都是一个区间，每个区间都被平均分为2个子区间，作为它的左右儿子。比如说区间[1，10]，被分为区间[1，5]作为左儿子，区间[6，10]作为右儿子：
为什么要设计这样奇怪的数据结构呢？
线段树主要适用于某些相对罕见的应用场景：
比如给定了若干元素，要求统计出不同区间范围内，元素的个数。
现在我们已经知道了什么是线段树，那么看一个利用线段树的例子。
线段树的存储与建造
这是一个序列：
现在我们要用它完成一个区间求和的任务。
区间求和就是指求序列中一段区间的所有元素之和。比如说上面的序列，区间[1，5]的和为元素1+元素2+元素3+元素4+元素5，也就是14。再举一个例子，区间[9，10]的和为9。
在学习线段树的概念的时候，我们就知道线段树的每个节点都存储了一个区间。比如说对于[1，10]这个节点，也就是这棵线段树的根节点，那么它的值为1+5+1+3+4+2+0+9+0+9=34。看我们把这棵树填完：
（当一个区间的左右边界已经相等时，比如[1，1]，表示这个区间内只有一个元素了，此时不能再分割，因此它就没有左右儿子节点了）
现在就让我们用代码实现线段树：
用一个类Node表示线段树的节点：
classNode{intl;//l是区间左边界intr;//r是区间右边界intsum;//sum是区间元素和publicNode(intl,intr,intsum){this.l=l;this.r=r;this.sum=sum;}}
线段树的任意节点都有3个属性：
区间的左边界l区间的右边界r区间的元素和sum比如说在上面的线段树中，区间[1,10]这个元素：
左边界为1右边界为10元素和为34定义元素个数、原序列和线段树
staticintn=10;//n是元素个数staticint[]array={0,1,5,1,3,4,2,0,9,0,9};//array是原序列(第一个0是占array[0]位的)staticNode[]tree=newNode[4*n];staticvoidinitTree(){for(inti=0;itree.length;i++){tree=newNode(0,0,0,0);}}
首先我们在上文已经定义了元素个数和原序列。他们的值如下：
元素个数为10个原序列为[0，1，5，1，3，4，2，0，9，0，9]现在问题在于：存储线段树的数组应该开多大的空间？根据证明发现，一个有n个元素的序列，所对应的线段树至少需要大小为4n的数组来存储。这一类证明网上有很多，读者可以自行查阅一下。
我们用inittree这个函数进行线段树初始化（tree数组初始值为null，不初始化会报错，我在这个地方卡了好久）
updateNode函数负责更新节点的值：
staticvoidupdateNode(intnum){//num是当前节点序号tree[num].sum=tree[num*2].sum+tree[num*2+1].sum;}
仔细观察前面的线段树可以发现，每一个节点的值都等于其左右儿子值的和。我们刚刚学会，一个编号为n的节点，其左右儿子分别为2n和2n+1。因此我们把num的值更新为2num+2num+1，也就是其左右儿子的和。
build函数建造线段树：
staticvoidbuild(intl,intr,intnum){//建树tree[num].l=l;tree[num].r=r;if(l==r){//l=r说明到达叶子节点tree[num].sum=array[l];return;}intmid=(l+r)/2;build(l,mid,num*2);//递归左儿子build(mid+1,r,num*2+1);//递归右儿子updateNode(num);}
函数从区间[l，r]开始递归遍历整棵线段树，每一次都递归它的左右儿子，到叶子节点时结束。递归每一个儿子时，都对它进行更新。这样下来就完成了整棵树的初始化。
线段树的单点修改
现在假如我们需要把第6个元素从2修改为3：
那么就会有很多的区间相应的改变。比如说区间[5，7]，从4+2+0=6变成了4+3+0=7。现在让我们手动模拟一下线段树的单点修改过程。这里假设我们需要把元素6从2变成3：
首先，从根节点开始遍历，发现含有元素6的区间是根节点的右儿子，与左儿子没有关系。因此将修改目标锁定到右儿子：
第二步，发现含有6的区间是左儿子，因此把目标放到左儿子上：
第三步同理：
第四步同理：
此时发现这是一个叶子节点，因此对它进行更新，从2变成3：
返回到上一层：
接下去同理：
然后我们跳过演示，读者可以自己试试看用同样的方法修改这棵树。最后修改完应该是这样的：
根节点最后应该从34变成35，我经常会忘记修改它的值，大家千万不要忘记修改它。
演示完以后我们分析一下时间复杂度。如果我们使用线段树修改元素，每次都是折半操作，相当于二分查找的速度，时间复杂度仅仅是对数级别，也就是O（logn）。
modify函数实现单点修改：
staticvoidmodify(inti,intvalue,intnum){//把元素i修改为值valueif(tree[num].l==tree[num].r){//到达叶子节点tree[num].sum=value;return;}intmid=(tree[num].l+tree[num].r)/2;if(i=mid){modify(i,value,num*2);//递归左儿子}else{modify(i,value,num*2+1);//递归右儿子}updateNode(num);}
这一段代码也不是很难。每一次我们都从根开始递归遍历。我们先判断要更改的元素属于当前节点的左儿子还是右儿子，并且递归到该节点。递归结束后更新当前节点的值。假如遍历到叶子节点，说明我们已经遍历到了想要修改的元素，那么我们直接把该节点的值修改为value就可以了。
到这里我们已经学会了单点修改的方法了。接下来让我们更进一步，学习区间修改。
线段树的区间修改
首先让我们明确一下区间修改的概念：
单点修改，大致是以下两个步骤：
找到需要修改的点；修改这个点。而区间修改是这样两个步骤：
找到需要修改的区间；修改这段区间内的所有点。好的，概念我们明白了，现在要知道如何实现这个功能。首先我们看一看区间修改可能的情况：
1、需要修改的区间包含在儿子之内：
为大家画个图：
我们看到需修改区间[6，8]包含在未修改区间的右儿子里。这种情况很简单，我们直接递归到右儿子即可。
2、需要修改的区间被拆开：
还是画一个图：
这时4属于左儿子，但是5和6属于右儿子。这怎么办呢？最直接的方法是把这个区间拆成两半，属于左儿子的放一边，属于右儿子的放一边，像这样：
两种情况分类讨论后，我们就要考虑如何修改区间了。
最简单的方法就是把这些区间挨个儿修改。但是大家可以试试看，这种方法比暴力还要慢好几倍。因此我们需要使用懒惰标记。
现在假如我们需要把区间[5，7]每个元素增加2：
首先，5属于根节点的左儿子，而6和7属于根节点的右儿子，因此两边都要进行修改。我们可以先修改左儿子：
5属于当前节点的右儿子，因此我们锁定右儿子：
5属于当前节点的右儿子，那么我们修改右儿子。我们发现右儿子就是5。当前只有一个元素，因此我们把当前的值+2，并为其打上一个懒惰标记，懒惰标记的值也是2：
之后向上回溯，每一个节点都进行更新，也就是说每一个节点都更新为其左儿子+右儿子，最后更新完是这样的：
到目前为止，懒惰标记还没有发挥作用，但是我们可以看一看6和7这段区间的修改。首先因为6和7在根节点的右儿子，因此我们先遍历右儿子：
接着因为6和7在当前节点的左儿子，因此我们遍历左儿子：
之后我们发现6和7就是当前节点的左儿子，因此我们直接遍历到左儿子，修改其值并打上懒惰标记。需要指出的是，因为6~7有2个元素，因此增加的值要乘2，也就是从+2变为+4，但懒惰标记的值不用乘2：
此时让我们思考一个问题：
我们还需要遍历修改[6，6]和[7，7]吗？
这时就不用了，因为我们已经打上了懒惰标记，懒惰标记的初衷就是延迟修改，因此我们当然不需要再修改这两个节点了。现在让我们一鼓作气，回溯到根节点，完成所有更新：
现在我们一起用代码实现：
为Node类添加懒惰标记：
classNode{intl;//l是区间左边界intr;//r是区间右边界intsum;//sum是区间元素和intlazy;//lazy是懒惰标记publicNode(intl,intr,intsum,intlazy){this.l=l;this.r=r;this.sum=sum;this.lazy=lazy;}}
新增了lazy变量作为懒惰标记。
modifySegment函数实现区间修改的代码：
staticvoidmodifySegment(intl,intr,intvalue,intnum){//[l,r]每一项都增加valueif(tree[num].l==ltree[num].r==r){//找到当前区间tree[num].sum+=(r-l+1)*value;//r-l+1是区间元素个数tree[num].lazy+=value;return;}intmid=(tree[num].l+tree[num].r)/2;if(r=mid){//在左区间modifySegment(l,r,value,num*2);}elseif(lmid){//在右区间modifySegment(l,r,value,num*2+1);}else{//分成2块modifySegment(l,mid,value,num*2);modifySegment(mid+1,r,value,num*2+1);}updateNode(num);}
首先，按照开始讲的3种情况，进行分类讨论（情况分别是：完全在左区间，完全在右区间，分成了2块），并且向下递归。
线段树的区间查询
区间查询，顾名思义就是查询一段区间内的元素和。那么如何实现呢？
不急，现在我们来看这样一种情况：
[1，2]有一个懒惰标记2。现在假如我要求[1，1]的值怎么办？
凉拌
为什么我这么说？因为[1，2]这个节点有一个懒惰标记，但是[1，1]却没有被更新，这是一个问题。
此时我们就要实现一个函数，用于把懒惰标记下传给儿子们，称为pushdown函数。下面直接给代码，解析部分请看代码解析吧：
使用pushdown函数下传懒惰标记：
staticvoidpushdown(intnum){if(tree[num].l==tree[num].r){//叶节点不用下传标记tree[num].lazy=0;//清空当前标记return;}tree[num*2].lazy+=tree[num].lazy;//下传左儿子的懒惰标记tree[num*2+1].lazy+=tree[num].lazy;//下传右儿子的懒惰标记tree[num*2].sum+=(tree[num*2].r-tree[num*2].l+1)*tree[num].lazy;//更新左儿子的值tree[num*2+1].sum+=(tree[num*2+1].r-tree[num*2+1].l+1)*tree[num].lazy;//更新右儿子的值tree[num].lazy=0;//清空当前节点的懒惰标记}
下传懒惰标记步骤有3步：
将懒惰标记传递给儿子；更新儿子的值；清空当前节点的懒惰标记。需要注意的是，叶子节点不用下传标记。
现在我们完成了pushdown函数的编写，可以开始学习区间查询了。刚才我们完成了区间修改，并且将原序列修改为了[1，5，1，3，6，4，2，9，0，9]。现在我们接着实现区间查询问题。假如我们要查询区间[5，6]：
正如我们所见，答案为10。现在告诉大家一个好消息，那就是区间查询的大致步骤其实和区间修改没有什么出入。让我们来实践一下：
首先，5和6分别属于根节点的左儿子和右儿子，那我们先遍历左儿子：
接着继续往下：
往下查找到[5，5]：
记录好这边答案为6。接着我们看根节点的右儿子，查找元素6：
向下搜索到[6，8]：
搜索到[6，7]：
此时我们需要下传[6，7]的懒惰标记，并且更新[6，6]的值，如下：
最后遍历到[6，6]，值为4，与刚才得到的6相加，答案就是10：
那么我们上代码：
query函数实现区间查询：
staticintquery(intl,intr,intnum){if(tree[num].lazy!=0){//下传懒惰标记pushdown(num);}if(tree[num].l==ltree[num].r==r){//找到当前区间returntree[num].sum;}intmid=(tree[num].l+tree[num].r)/2;if(r=mid){//在左区间returnquery(l,r,num*2);}if(lmid){//在右区间returnquery(l,r,num*2+1);}returnquery(l,mid,num*2)+query(mid+1,r,num*2+1);//分成2块}
步骤与区间修改完全相同，记得要pushdown一下就行。
思考与探究
下面让我们进行一些对于线段树的思考与探究：
线段树都应用于什么环境？除了区间和外，能否解决更多问题？比起别的树有什么优势？
线段树一般多用于区间问题。在本文中我们解决的是区间和，但是也能解决更多的问题，比如区间平方和等等。线段树只能解决符合下面条件的问题：
当区间[l，r]可以由[l，mid(l，r)]和[mid(l，r)+1，r]得到答案
我们举几个满足条件的例子：
区间[5，8]的区间和，可以由[5，6]的区间和加上[7，8]的区间和得到。区间[5，8]的最小值，等于区间[5，6]的最小值与[7，8]的最小值的最小值。但是还有一些不满足条件：
区间[5，8]的最长上升子序列。另外就是线段树比起别的树的特点。线段树属于二叉搜索树，像我们熟悉的红黑树、AVL树其实也都属于二叉搜索树。只不过不同的二叉搜索树用处不相同。线段树比起别的树，它的最大特点就是用作存储区间的特性。
线段树和前缀和算法有什么优劣区别吗？
写到这里并不清楚各位是否明白前缀和算法。这里给大家简单介绍一下：
对于任何一个序列，都能制作一个相对应的前缀和数组。对于一个序列来讲，假如我们用pre表示前缀和数组，那么pre就表示区间[1，i]的区间和，比如pre[3]为array[1]+array[2]+array[3]，也就是7。
现在我们可用pre表示区间[1，i]，那么假如有一个任意区间[l，r]，我们应该怎么表示它的区间和呢？仔细思考一下不难发现，区间[l，r]的区间和其实就是区间[1，r]减去区间[1，l-1]，剩下的也就是区间[l，r]了。因此我们可用pre[r]-pre[l-1]表示。
举个例子，区间[3，5]的和为1+3+4=8，相当于区间[1，5]减去区间[1，(3-1)]，也就是14-6=8。
我们发现，使用前缀和只要做一个减法就能得到区间和，而线段树还要遍历好多次，那是不是说，前缀和甚至要快于线段树呢？我们可以来对比一下线段树和前缀和的时间复杂度：
线段树的完整代码
最后，附上线段树的完整代码实现：
staticintn=10;//n是元素个数staticint[]array={0,1,5,1,3,4,2,0,9,0,9};//array是原序列(第一个0是占array[0]位的)staticNode[]tree=newNode[4*n];//tree是线段树publicstaticvoidmain(String[]args){initTree();build(1,10,1);//利用build函数建树System.out.println(操作1：[2，5]的区间和是：+query(2,5,1));//利用query函数搜索区间和modify(5,9,1);//利用modify函数实现单点修改（元素5从4改为9）System.out.println(操作2：元素5从4改为9，此时[2，5]的区间和是：+query(2,5,1));modifySegment(3,4,3,1);//利用modifySegment函数将[3，4]每个元素增加3System.out.println(操作3：区间[3，4]每个元素+3，此时[2，5]的区间和是：+query(2,5,1));}staticvoidinitTree(){for(inti=0;itree.length;i++){tree=newNode(0,0,0,0);}}staticvoidupdateNode(intnum){//num是当前节点序号tree[num].sum=tree[num*2].sum+tree[num*2+1].sum;}staticvoidbuild(intl,intr,intnum){//建树tree[num].l=l;tree[num].r=r;if(l==r){//l=r说明到达叶子节点tree[num].sum=array[l];return;}intmid=(l+r)/2;build(l,mid,num*2);//递归左儿子build(mid+1,r,num*2+1);//递归右儿子updateNode(num);}staticvoidmodify(inti,intvalue,intnum){//把元素i修改为值valueif(tree[num].l==tree[num].r){//到达叶子节点tree[num].sum=value;return;}intmid=(tree[num].l+tree[num].r)/2;if(i=mid){modify(i,value,num*2);//递归左儿子}else{modify(i,value,num*2+1);//递归右儿子}updateNode(num);}staticvoidmodifySegment(intl,intr,intvalue,intnum){//[l,r]每一项都增加valueif(tree[num].l==ltree[num].r==r){//找到当前区间tree[num].sum+=(r-l+1)*value;//r-l+1是区间元素个数tree[num].lazy+=value;return;}intmid=(tree[num].l+tree[num].r)/2;if(r=mid){//在左区间modifySegment(l,r,value,num*2);}elseif(lmid){//在右区间modifySegment(l,r,value,num*2+1);}else{//分成2块modifySegment(l,mid,value,num*2);modifySegment(mid+1,r,value,num*2+1);}updateNode(num);}staticvoidpushDown(intnum){if(tree[num].l==tree[num].r){//叶节点不用下传标记tree[num].lazy=0;//清空当前标记return;}tree[num*2].lazy+=tree[num].lazy;//下传左儿子的懒惰标记tree[num*2+1].lazy+=tree[num].lazy;//下传右儿子的懒惰标记tree[num*2].sum+=(tree[num*2].r-tree[num*2].l+1)*tree[num].lazy;//更新左儿子的值tree[num*2+1].sum+=(tree[num*2+1].r-tree[num*2+1].l+1)*tree[num].lazy;//更新右儿子的值tree[num].lazy=0;//清空当前节点的懒惰标记}staticintquery(intl,intr,intnum){if(tree[num].lazy!=0){//下传懒惰标记pushDown(num);}if(tree[num].l==ltree[num].r==r){//找到当前区间returntree[num].sum;}intmid=(tree[num].l+tree[num].r)/2;if(r=mid){//在左区间returnquery(l,r,num*2);}if(lmid){//在右区间returnquery(l,r,num*2+1);}returnquery(l,mid,num*2)+query(mid+1,r,num*2+1);//分成2块}staticclassNode{intl;//l是区间左边界intr;//r是区间右边界intsum;//sum是区间元素和intlazy;//lazy是懒惰标记publicNode(intl,intr,intsum,intlazy){this.l=l;this.r=r;this.sum=sum;this.lazy=lazy;}}
需要特别说的的是，投稿的王乙堃同学年仅12岁，在读小学六年级，能写出这样的文章真的很了不起！