小学六年级学生写的 “线段树”解析，厉害了！

查看原文

其他

小学六年级学生写的 “线段树”解析，厉害了！

程序人生 2020-12-18

The following article is from 程序员小灰 Author 王乙堃

作者 | 王乙堃

来源 | 程序员小灰

线段树是一个复杂的数据结构，比较难理解，也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候，我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。

这篇文章比较长，建议大家耐心阅读，好好消化吸收哦~~

前置内容

学习线段树前，你需要掌握二叉搜索树，我只补充一个内容，就是关于二叉搜索树如何编号。

二叉搜索树的根节点编号为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，我经常会忘记修改它的值，大家千万不要忘记修改它。

演示完以后我们分析一下时间复杂度。如果我们使用线段树修改元素，每次都是折半操作，相当于二分查找的速度，时间复杂度仅仅是对数级别，也就是O（logn）。

【代码片段 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 就可以了。

到这里我们已经学会了单点修改的方法了。接下来让我们更进一步，学习区间修改。

线段树的区间修改

首先让我们明确一下区间修改的概念：

单点修改，大致是以下两个步骤：

找到需要修改的点；
修改这个点。

而区间修改是这样两个步骤：

找到需要修改的区间；
修改这段区间内的所有点。

好的，概念我们明白了，现在要知道如何实现这个功能。首先我们看一看区间修改可能的情况：

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]吗？

这时就不用了，因为我们已经打上了懒惰标记，懒惰标记的初衷就是延迟修改，因此我们当然不需要再修改这两个节点了。现在让我们一鼓作气，回溯到根节点，完成所有更新：

现在我们一起用代码实现：

【代码片段 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。

我们发现，使用前缀和只要做一个减法就能得到区间和，而线段树还要遍历好多次，那是不是说，前缀和甚至要快于线段树呢？我们可以来对比一下线段树和前缀和的时间复杂度：

线段树的完整代码

最后，附上线段树的完整代码实现：

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;
    }
}