线段树是刷题中一种常用的数据结构，其可以在O(logN)的复杂度内实现修改单个点、修改区间、区间求和、区间最大值、区间最小值等操作。那么线段树究竟是如何做到这一点的、线段树用代码又该如何实现，借着植树节的这个时间，我来浅析（学习）一下线段树的方方面面。

组成与构建

简单点说，线段树就是由“区间”组成的二叉树，其结点表示的是某段区间上的区间和，而结点的子结点便是区间的左子区间和右子区间。

假如有一个长度为 6 的数组[1,2,3,4,5,6]，我们便可构建如下的线段树。其中我们用d(n)表示编号为n的结点所存储的数值，即结点所保存的区间上的区间和。观察这棵树的性质，我们首先可以发现这是一棵完全二叉树，且其叶子结点所表示区间的区间长度均为 1。同时对于一个节点n，假设其表示的区间为[l,r]，那么它左子结点编号为2n，所表示的区间长度为[l,\frac{l+r}{2}]，而右子结点编号为2n+1，所表示的区间长度为[\frac{l+r}{2}+1,r]。而如果采用这样的存储方式，那么假设有n个叶子结点，即原数组长度为n的话，数组d的长度最多为2^{\left \lceil log n \right \rceil +1}（一般开 4n 的空间就够用；证明见参考资料）。

根据这样的性质，我们可以轻易地构建出一棵线段树。假设原数组为a，要将其转化为一棵线段树。首先对于一个结点n，设其表示的区间为[l,r]。如果l=r，那么意味着其区间长度为 1，也就有d[n]=a[l]=a[r]。否则，我们可以通过其子结点的d[n]得到，即d[n]=d[2n]+d[2n+1]。那么他的子结点的d[n]如何得到呢，很简单，把上面这个过程重复一遍即可。

也就是说构建线段树的过程本质上是从根结点向下递归的过程，递归边界即是l=r。

区间查询

依旧以上图为例，如果我们要查询区间[4,6]的值，直接返回d[3]=15即可。那如果我们要查询区间[2,6]的值呢。区间[2,6]可以分解为区间[2,3]和区间[4,6]的值之和，而其中的区间[2,3]也可以进一步分解为区间[2,2]和区间[3,3]的值之和。同样我们发现区间查询也是一个不断递归的过程。

那么其具体规则是怎样的呢，我们如何知道返回哪个d[n]是正确的。很简单，如果我们要求区间[s,t]的区间和，那么它的“分解区间”必定是它的子集，而由线段树的性质可知，如果某个结点所表示的区间[l,r]不是[s,t]的子集，而它又和[s,t]有交集，那么[l,r]的子区间中必然存在属于[s,t]子集的区间。同样，使用这样的区间拆分也不存在某个区间算两次的问题。于是，经过子集、交集的判断，我们便可以通过递归求得所需区间的区间和。

区间修改

区间修改是线段树高效的核心，毕竟单点修改、区间查询这种问题前缀和就能在O(1)复杂度内解决。

线段树之所以能够在如此短的时间内做到区间修改，关键在于“懒惰标记”。在此处为了引入懒惰标记，我引用一下 OI Wiki 上的例子。

A 有两个儿子，一个是 B，一个是 C。

有一天 A 要建一个新房子，没钱。刚好过年嘛，有人要给 B 和 C 红包，两个红包的钱数相同都是 元，然而因为 A 是父亲所以红包肯定是先塞给 A 咯~

理论上来讲 A 应该把两个红包分别给 B 和 C，但是……缺钱嘛，A 就把红包偷偷收到自己口袋里了。

A 高兴地说：「我现在有 2 份红包了！我又多了 2 元了！哈哈哈~」

但是 A 知道，如果他不把红包给 B 和 C，那 B 和 C 肯定会不爽然后导致家庭矛盾最后崩溃，所以 A 对儿子 B 和 C 说：「我欠你们每人 份 元的红包，下次有新红包给过来的时候再给你们！这里我先做下记录……嗯……我欠你们各 1 元……」

儿子 B、C 有点恼怒：「可是如果有同学问起我们我们收到了多少红包咋办？你把我们的红包都收了，我们还怎么装？」

父亲 A 赶忙说：「有同学问起来我就会给你们的！我欠条都写好了不会不算话的！」

这样 B、C 才放了心。

懒惰标记正如故事中的“欠条”。当我们要求修改区间值加上某个数后，我们并不会直接加到那段区间上，而是先将其加在整个大区间里。直到“有同学问”时欠条才会更新，也就是直到我们查询某段区间的值时，包含这段区间的大区间上的懒惰标记才会逐步下传到查询区间，查询区间收到懒惰标记后就会加上已有的值直接返回区间和，不再下传标记。因此我们可以实现问哪里加哪里，降低复杂度的同时减少资源浪费。

那么具体应该如何实现懒惰标记的记录和下传。这里需要我们用一个懒惰标记数组m[n]表示编号为n的结点上的懒惰标记的值。我们依然以上图为例，假设我们为区间[2,6]的每一个元素增加 3，首先从根结点d[1]开始，因为d[1]所表示的区间并不是区间[2,6]的子区间，并且d[1]上也没有之前的懒惰标记不用下传，因此可以直接寻找d[1]子结点中和所需区间有交集的部分（原理同上区间查询）。所以我们首先找到了区间[1,2]和[3,3]，对于区间[1,2]重复刚才的操作，而对于[3,3]，这是所需区间的子区间，因此我们可以直接将其打上懒惰标记，即m[5]+=3，同时更新其区间和d[5]+=(3-3+1)*m[5]=6，至此我们应该已经为区间[2,2]，[3,3]都打上了懒惰标记并更新了区间和，因此为了使得上层大区间的区间和也能够响应这个变化，我们还需要将所更新的区间和返回以更新大区间的区间和。没错，就是递归，也就是当我们在区间[1,3]向下修改完子结点后，再更新区间和，即d[n]=d[2n]+d[2n+1]。

同理对于另一边的区间[4,6]，我们可以直接修改其区间和和懒惰标记。至此我们实现了第一次区间更新。之后多次区间更新基本都是这样的步骤，唯一的不同是，在之后的区间更新时，如果大区间中已经有一个懒惰标记，我们理应继续探索其子区间以增加懒惰标记和区间和，但是部分题目中不断增加懒惰标记可能导致数据溢出，因此我们常常在区间更新时，直接将大区间中上一次的懒惰标记下传，然后再探索子区间。

之后我们也需要略微改一下区间查询的步骤。如上述例子中的区间[4,6]，它在第一次更新之后有一个懒惰标记 3 还没有下传到子区间，而如果我们尝试询问区间[6,6]的值，按照区间查询的步骤，我们在递归至[4,6]时应该直接向下寻找子区间，但在区间更新中我们只更新了区间[4,6]的区间和，因此如果我们要查询它的子区间的区间和，我们首先应该将标记下传。也就是说，当区间查询时，如果区间上存在尚未清空的懒惰标记，我们需要将标记下传到指定区间，并清空区间上的标记。

至此我们实现了在O(logN)时间复杂度下的区间更新。

总结

写的略菜，毕竟我也是现学现用，甚至连题都还没做（这个会在“线段树浅析-下”中更新），中间很多文字阐述的部分可能过长，显得较为晦涩难懂，建议去 OI Wiki 上看一看图和代码实现（这个也会在之后更新），尤其要看代码实现，哪怕不做题、哪怕把自己当作人肉编译器，也要看明白代码实现，这是算法转化为实现的最重要的一步。同样网络上还有很多（比我写得好的）博客，可以拿来参考。

同时这篇博客也只是讲了最基本的线段树知识，也就是原理、构建、使用之类的。具体操作中线段树还有很多高端技巧，如“当懒惰标记累加不会发生溢出时，可以在区间更新时不下传标记”的标记持久化，“修改区间中所有元素为特定值”，“非递归线段树”等。具体也可以参考其他大佬的博客（Orz）。

虽说线段树仅仅是竞赛题目中较为常见的一种数据结构，但是线段树的高效率，以及它作为一种算法和数据结构所蕴含的思想是值得我们深入学习的。（也不保证随着内卷加剧线段树不会出现在面试中）

大概就是这些。最后，植树节快乐，希望世界上的程序员每写一棵树，地球就能多出一点绿色。