一文讲解“线段树”到底是什么
线段树是一个复杂的数据结构，比较难理解，也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候，我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。
这篇文章比较长，建议大家耐心阅读，好好消化吸收哦~~
前置内容
学习线段树前，你需要掌握二叉搜索树，不太了解的小伙伴，可以看看小灰之前发布的红黑树漫画，前半部分讲解了二叉搜索树：
我只补充一个内容，就是关于二叉搜索树如何编号。
二叉搜索树的根节点编号为1，对于每个节点，假如其编号为N，它的左儿子编号为2N，右儿子编号为2N+1。因此，整个二叉搜索树的编号如下：
上图当中，结点上方的数字是结点的编号，后续为了简单，把编号写在结点内不。
有读者可能要问了，为什么3的儿子是6和7，而不是4和5呢？这是因为虽然节点4和节点5不存在，但是仍然应该为他们保留4和5这2个编号，你可以把这棵树看成这样：
线段树的概念
线段树，英文名称是Segment Tree，其本质也是一个二叉搜索树，区别在于线段树的每一个节点记录的都是一个区间，每个区间都被平均分为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]，表示这个区间内只有一个元素了，此时不能再分割，因此它就没有左右儿子节点了）
现在就让我们用代码实现线段树：
【代码片段 1】 用一个类Node表示线段树的节点：
class Node {
int l; // l是区间左边界
int r; // r是区间右边界
int sum; // sum是区间元素和
public Node (int l, int r, int sum){
this.l = l;
this.r = r;
this.sum = sum;
}
}
【代码解析 1】 线段树的任意节点都有3个属性：
- 区间的左边界l
- 区间的右边界r
- 区间的元素和sum
比如说在上面的线段树中，区间[1,10]这个元素：
- 左边界为1
- 右边界为10
- 元素和为34
【代码片段 2】 定义元素个数、原序列和线段树
static int n = 10; // n是元素个数
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
// array是原序列(第一个0是占array[0]位的)
static Node[] tree = new Node[4*n];
static void initTree (){
for(int i = 0; i < tree.length; i++){
tree[i] = new Node(0, 0, 0, 0);
}
}
【代码解析 2】 首先我们在上文已经定义了元素个数和原序列。他们的值如下：
- 元素个数为10个
- 原序列为[0，1，5，1，3，4，2，0，9，0，9]
现在问题在于，存储线段树的数组应该开多大的空间？根据证明发现，一个有n个元素的序列，所对应的线段树至少需要大小为4n的数组来存储。这一类证明网上有很多，读者可以自行查阅一下。
我们用inittree这个函数进行线段树初始化（tree数组初始值为null，不初始化会报错，我在这个地方卡了好久）
【代码片段 3】 updateNode函数负责更新节点的值：
static void updateNode (int num) { // num是当前节点序号
tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}
【代码解析 3】 仔细观察前面的线段树可以发现，每一个节点的值都等于其左右儿子值的和。我们刚刚学会，一个编号为n的节点，其左右儿子分别为2n和2n+1。因此我们把num的值更新为2num+2num+1，也就是其左右儿子的和。
【代码片段 4】 build函数建造线段树：
static void build (int l, int r, int num) { // 建树
tree[num].l = l;
tree[num].r = r;
if (l == r) { // l = r说明到达叶子节点
tree[num].sum = array[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, num * 2); // 递归左儿子
build(mid + 1, r, num * 2 + 1); // 递归右儿子
updateNode(num);
}
【代码解析 4】 函数从区间[l，r]开始递归遍历整棵线段树，每一次都递归它的左右儿子，到叶子节点时结束。递归每一个儿子时，都对它进行更新。这样下来就完成了整棵树的初始化。
线段树的单点修改
现在假如我们需要把第6个元素从2修改为3：
那么就会有很多的区间相应的改变。比如说区间[5，7]，从4+2+0=6变成了4+3+0=7。现在让我们手动模拟一下线段树的单点修改过程。这里假设我们需要把元素6从2变成3：
首先，从根节点开始遍历，发现含有元素6的区间是根节点的右儿子，与左儿子没有关系。因此将修改目标锁定到右儿子：
第二步，发现含有6的区间是左儿子，因此把目标放到左儿子上：
第三步同理：
第四步同理：
此时发现这是一个叶子节点，因此对它进行更新，从2变成3：
返回到上一层：
接下去同理：
然后我们跳过演示，读者可以自己试试看用同样的方法修改这棵树。最后修改完应该是这样的：
根节点最后应该从34变成35，我经常会忘记修改它的值，大家千万不要忘记修改它。
演示完以后我们分析一下时间复杂度。如果我们使用线段树修改元素，每次都是折半操作，相当于二分查找的速度，时间复杂度仅仅是对数级别，也就是 。
【代码片段 5】 modify函数实现单点修改：
static void modify (int i, int value, int num) { // 把元素i修改为值value
if (tree[num].l == tree[num].r) { // 到达叶子节点
tree[num].sum = value;
return;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (i <= mid) {
modify(i, value, num * 2); // 递归左儿子
}
else {
modify(i, value, num * 2 + 1); // 递归右儿子
}
updateNode(num);
}
【代码解析 5】 这一段代码也不是很难。每一次我们都从根开始递归遍历。我们先判断要更改的元素属于当前节点的左儿子还是右儿子，并且递归到该节点。递归结束后更新当前节点的值。假如遍历到叶子节点，说明我们已经遍历到了想要修改的元素，那么我们直接把该节点的值修改为value就可以了。
到这里我们已经学会了单点修改的方法了。接下来让我们更进一步，学习区间修改。
线段树的区间修改
首先让我们明确一下区间修改的概念：
单点修改，大致是以下两个步骤：
- 找到需要修改的点
- 修改这个点
而区间修改是这样两个步骤：
- 找到需要修改的区间
- 修改这段区间内的所有点
好的，概念我们明白了，现在要知道如何实现这个功能。首先我们看一看区间修改可能的情况：
- 需要修改的区间包含在儿子之内：为大家画个图：我们看到需修改区间[6，8]包含在未修改区间的右儿子里。这种情况很简单，我们直接递归到右儿子即可。
- 需要修改的区间被拆开：还是画一个图：这时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]吗？
这时就不用了，因为我们已经打上了懒惰标记，懒惰标记的初衷就是延迟修改，因此我们当然不需要再修改这两个节点了。现在让我们一鼓作气，回溯到根节点，完成所有更新：
现在我们一起用代码实现：
【代码片段 6】 为Node类添加懒惰标记：
class Node {
int l; // l是区间左边界
int r; // r是区间右边界
int sum; // sum是区间元素和
int lazy; // lazy是懒惰标记
public Node (int l, int r, int sum, int lazy){
this.l = l;
this.r = r;
this.sum = sum;
this.lazy = lazy;
}
}
【代码解析 6】 新增了lazy变量作为懒惰标记。
【代码片段 7】 modifySegment函数实现区间修改的代码：
static void modifySegment(int l, int r, int value, int num) { // [l,r]每一项都增加value
if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
tree[num].sum += ( r - l + 1 ) * value; // r-l+1是区间元素个数
tree[num].lazy += value;
return;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (r <= mid) { // 在左区间
modifySegment(l, r, value, num * 2);
}
else if (l > mid) { // 在右区间
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);
}
【代码解析 7】 首先，按照开始讲的3种情况，进行分类讨论（情况分别是：完全在左区间，完全在右区间，分成了2块），并且向下递归。
线段树的区间查询
区间查询，顾名思义就是查询一段区间内的元素和。那么如何实现呢？
不急，现在我们来看这样一种情况：
[1，2]有一个懒惰标记2。现在假如我要求[1，1]的值怎么办？
凉拌
为什么我这么说？因为[1，2]这个节点有一个懒惰标记，但是[1，1]却没有被更新，这是一个问题。
此时我们就要实现一个函数，用于把懒惰标记下传给儿子们，称为pushdown函数。下面直接给代码，解析部分请看代码解析吧：
【代码片段 8】 使用pushdown函数下传懒惰标记：
static void pushdown (int num) {
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; // 清空当前节点的懒惰标记
}
【代码解析 8】 下传懒惰标记步骤有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：
那么我们上代码：
【代码片段 9】 query函数实现区间查询：
static int query (int l, int r, int num) {
if (tree[num].lazy != 0) { // 下传懒惰标记
pushdown(num);
}
if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
return tree[num].sum;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (r <= mid) { // 在左区间
return query(l, r, num * 2);
}
if (l > mid) { // 在右区间
return query(l, r, num * 2 + 1);
}
return query(l, mid, num * 2) + query(mid + 1, r, num * 2 + 1); // 分成2块
}
【代码解析 9】 步骤与区间修改完全相同，记得要pushdown一下就行。
思考与探究
下面让我们进行一些对于线段树的思考与探究：
【思考 1】 线段树都应用于什么环境？除了区间和外，能否解决更多问题？比起别的树有什么优势？
【答案 1】 线段树一般多用于区间问题。在本文中我们解决的是区间和，但是也能解决更多的问题，比如区间平方和等等。线段树只能解决符合下面条件的问题：
当区间[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树其实也都属于二叉搜索树。只不过不同的二叉搜索树用处不相同。线段树比起别的树，它的最大特点就是用作存储区间的特性。
【思考 2】 线段树和前缀和算法有什么优劣区别吗？
【答案 2】 写到这里并不清楚各位是否明白前缀和算法。这里给大家简单介绍一下：
对于任何一个序列，都能制作一个相对应的前缀和数组。对于一个序列来讲，假如我们用pre表示前缀和数组，那么pre[i]就表示区间[1，i]的区间和，比如pre[3]为array[1]+array[2]+array[3]，也就是7。
现在我们可用pre[i]表示区间[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。
我们发现，使用前缀和只要做一个减法就能得到区间和，而线段树还要遍历好多次，那是不是说，前缀和甚至要快于线段树呢？我们可以来对比一下线段树和前缀和的时间复杂度：
算法名称初始化修改查询前缀和O(n)O(n)O(1)线段树O(log n)O(log n)O(log n)
我们发现，线段树比起前缀和有更加稳定的特点。它的每一项都是对数级别。而前缀和虽然查询非常快，但是修改速度就相对慢很多。因此我们认为，假如不需要进行元素的修改操作，那么我们一般选择前缀和。如果需要进行元素修改操作，那么线段树更为合适。
线段树的完整代码
最后，附上线段树的完整代码实现：
static int n = 10; // n是元素个数
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
// array是原序列(第一个0是占array[0]位的)
static Node[] tree = new Node[4*n]; // tree是线段树
public static void main(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]每个元素增加3
System.out.println("操作3：区间[3，4]每个元素+3，此时[2，5]的区间和是：" + query(2, 5, 1));
}
static void initTree (){
for(int i = 0; i < tree.length; i++){
tree[i] = new Node(0, 0, 0, 0);
}
}
static void updateNode (int num) { // num是当前节点序号
tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}
static void build (int l, int r, int num) { // 建树
tree[num].l = l;
tree[num].r = r;
if (l == r) { // l = r说明到达叶子节点
tree[num].sum = array[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, num * 2); // 递归左儿子
build(mid + 1, r, num * 2 + 1); // 递归右儿子
updateNode(num);
}
static void modify (int i, int value, int num) { // 把元素i修改为值value
if (tree[num].l == tree[num].r) { // 到达叶子节点
tree[num].sum = value;
return;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (i <= mid) {
modify(i, value, num * 2); // 递归左儿子
}
else {
modify(i, value, num * 2 + 1); // 递归右儿子
}
updateNode(num);
}
static void modifySegment(int l, int r, int value, int num) { // [l,r]每一项都增加value
if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
tree[num].sum += ( r - l + 1 ) * value; // r-l+1是区间元素个数
tree[num].lazy += value;
return;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (r <= mid) { // 在左区间
modifySegment(l, r, value, num * 2);
}
else if (l > mid) { // 在右区间
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);
}
static void pushDown(int num) {
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; // 清空当前节点的懒惰标记
}
static int query (int l, int r, int num) {
if (tree[num].lazy != 0) { // 下传懒惰标记
pushDown(num);
}
if (tree[num].l == l && tree[num].r == r) { // 找到当前区间
return tree[num].sum;
}
int mid = (tree[num].l + tree[num].r) / 2;
if (r <= mid) { // 在左区间
return query(l, r, num * 2);
}
if (l > mid) { // 在右区间
return query(l, r, num * 2 + 1);
}
return query(l, mid, num * 2) + query(mid + 1, r, num * 2 + 1); // 分成2块
}
static class Node {
int l; // l是区间左边界
int r; // r是区间右边界
int sum; // sum是区间元素和
int lazy; // lazy是懒惰标记
public Node (int l, int r, int sum, int lazy){
this.l = l;
this.r = r;
this.sum = sum;
this.lazy = lazy;
}
}
