图解：什么是线段树？

作者简介：黄子桓，华师大三学生一枚，进场参加各类算法竞赛，并获得了挺多荣誉，耗费 3 天时间给大家贡献此文！

图文：黄子桓

编辑：景禹

致谢：感谢子桓的无私贡献，收到您的投稿已有时日，只是我工作时间紧张，未能尽早修改发布，还望理解！祝愿你早日找到自己理想的工作。

简介

线段树是在算法竞赛中常用来维护区间信息的数据结构，同时，线段树的理解难度较树状数组低（当然是在理解递归的前提下）。

线段树可以在 的时间复杂度内实现对数组的单点修改、区间修改、区间查询等操作。

下面以一个简单的例题进行介绍：

给定一个数组 arr[0 ... n-1]，执行不超过10万次以下两个操作：

1、输出数组中 [left, right] 区间内的数的和，也就是 a[left] + a[l+1] + ... + a[right]

2、将数组 [left, right] 区间内的所有数更改为 k。

线段树的结构与建树

线段树将每个长度不为1的区间划分为左右两个区间，并递归处理，通过合并左右两个区间的信息来求得该区间的信息。

对于例题来说，我们想要得到的是指定区间里数的和，那么，我们要求的区间信息便是该区间数的和，合并左右两个区间的信息即是将两个区间的值进行相加。

例如对于数组 arr = [ 13 , 99 , 23 , 66 , 7 , 2 , 56 , 45 ] 而言：

数组长度为 8，以中点为分界点，划分为左右子区间：

设 mid = (left + right) / 2 ，则 [left, mid] 为左子区间，[mid + 1 , right]  为右子区间（如果区间长度是奇数，则左子区间比右子区间大1）；接着，对子区间递归划分，直到区间长度为 1。

我们对数组 arr = [ 13, 99, 23 , 66 , 7 , 2 , 56 , 45 ] 执行上面提到的递归划分过程后：

在回溯的过程中，合并子区间的信息，即将子节点的值加起来：

此时一颗线段树其实就已经建成了，你可以将你的手机上下颠倒看一看这个图。

线段树的结构如下：

如何存储这个线段树呢?

最简单的方法是堆式建树

即像下面这样，我们可以用一个数组直接存储线段树的节点，节点在数组中下标如图：

由图，我们可以发现一个规律：

对于一个节点，设其在数组中下标为 ，则该节点的左子节点的下标为  ，右子节点的下标为  ，父节点的下标为  (取下界)。

建树的代码：

int arr[100010];//原数组
int tree[400010]; //线段树数组
//建立线段树，[l, r]为节点代表的范围， p 为节点在线段树数组的下标
void build(int left, int right, int p = 1)
{
    if(left == right)
    {//区间长度为 1， 节点值即为原数组对应位置的值；
        tree[p] = arr[left];
        return;
    }
    int mid = (left + right)/2;
    
    build(left, mid, 2 * p); //递归处理左子区间
    build(mid + right, right, 2 * p + 1); //递归处理右子区间
    
    tree[p] = tree[2 * p] + tree[2 * p + 1]; // 合并左右子区间的信息
}


这里有一点需要注意：堆式建树的线段树的数组大小需要设为原数组大小的4倍，原理可参考

线段树需要开4倍区间大小的数组的原因 ，所以线段树节点数一定小于原区间长度的4倍，所以建树过程的时间复杂度为 量级。

区间查询

回到例题，建好树后，如何查询 [left, right] 区间内数的和？

只需要在线段树中找到一些节点，这些节点刚好能组成查询的区间，再合并这些节点的信息即可

（找到的节点要尽可能少）。

这里先放4张图，看一下查询过程以及我们需要查询的节点。

查询区间 [1, 5] :

查询区间的数的和即是 201+7=208 .

查询区间 [3, 6]：

查询区间的数的和即是 89+9=98

查询区间 [5, 6] :

查询区间的数的和即是 9

查询区间  [1, 7] :

查询区间的数的和即是 201+9+56=266

由图可以看出，在线段树中查询指定的区间，其实就是找到一些节点（也就是图中的粉红色节点），使这些节点恰好能组成查询的区间。

显然，查询操作所遍历的节点数（浅蓝色节点+粉红色节点）与树高成正比，即查询操作的时间复杂度为 .

为了查找这些浅蓝色节点，从根向下遍历，每遇到一个节点，可分为2种情况

1、当前节点代表的区间是询问区间的子集。

例如：询问区间为 [1, 7] ，当前节点代表的区间为 [1, 4] （大圆圈起部分）是询问区间的子集，则直接将此节点的值返回即可，区间 [5, 6] 和 [7] 也是一样。

可以发现，情况1的节点即是图中的粉红色节点。

2、除第一种情况外，判断询问节点与子区间是否有交集，若有，则递归处理。

例如：询问区间为 [1, 7] ，当前节点代表区间为  [1, 8] （大圆圈起部分）与询问区间有交集，则递归处理其左右孩子。

左子区间为 [1, 4] ，是询问区间 [1,7] 的子集，所以将其返回 sum = 201；

右子区间为  [5, 8]  ，与询问区间 [1,7] 有交集，递归调用其左右子节点；

[5,8]  的左子区间 [5,6] ，是询问区间 [1,7] 的子集，所以将其返回 sum = 201 + 9 = 210;

[5,8]  的右子区间 [7,8] ，与询问区间 [1,7] 有交集，递归调用其左右子节点；

[7,8] 的左子区间 [7] ，是询问区间的子集，所以将其直接返回 sum = 210 + 56 = 276；

[7,8] 的右子区间 [8] ，与询问区间不存在子集也不存在交集，回溯到根结点结束。

情况2其实就是图中浅蓝色节点，递归完成后合并信息并返回。

那么如何判断两个区间是否有交集？

如果询问区间的 左 端点 小于等于 当前节点区间的 分界点，则为左子区间相交。

比如当前结点区间为 [1,8]，其分界点为 mid = (1+8)/2=4 ，查询区间为 [1,7] ，查询区间的左端点为 1 ，由于 1 < 4 ，所以查询区间与当前结点区间为左子区间相交。

如果询问区间的 右 端点 大于 当前节点区间的 分界点，则与右子区间相交。

比如当前结点区间为 [1,8]，其分界点为 mid = (1+8)/2=4 ，查询区间为 [5,6] ，查询区间的右端点为 6 ，由于 6 > 4 ，所以查询区间与当前结点区间为右子区间相交。

只看两种情况的描述有点抽象，直接看整体的代码：

int query(int nl, int nr, int l, int r, int p = 1){//[nl, nr]为所访问区间，[l, r]为当前结点代表的区间    if(nl <= l && r <= nr)    {        return tree[p];    }

    int mid = (l + r) / 2;    int sum = 0;    if(l <= mid)    {        sum += query(nl, nr, l, mid, 2 * p);    }    if(r > mid)    {        sum += query(nl, nr, mid+1, r, 2 * p + 1);    }    return sum;}

单点修改

看完前两个步骤的代码，相信已经发现了：线段树的一系列操作就是通过递归不断缩小区间，直到找到所需的节点。

那么单点修改的操作就很明显了：找到对应的区间并修改，回溯时对沿途的节点更新。

我们以将数组 arr[4] 的值 66 修改为 8 进行说明，其中 '递归' 递 的过程就是找到从根节点 [1,8] 到要修改的结点的 [4] 的路径，而 归 的过程就是对路径上结点值的修改过程。

修改结点 [4] 的值为 8 ：

修改结点 [4] 的父结点 [3,4] 的值为当前 [3] 的值 23 加上 [4] 的值 8 ，即 23 + 8 = 31 ：

修改节点 [3,4] 的父结点 [1,4] 的值为当前 [3,4] 节点的值 31 和其兄弟节点[1,2] 的值 112 的和，即 112 + 31 = 143：

最后将根节点 [1,8] 的值修改为当前结点 [1,4] 及其兄弟结点 [5,8] 的和，即 143 + 110 = 253:

实现代码超级简单（这就是递归的魅力，代码简洁）：

void change_s(int idx, int k, int l, int r, int p = 1)
{// 将arr[idx] 的值修改为 k, [l, r] 为当前结点代表的区间
    if(l == idx && r == idx)
    {
        tree[p] = k;
        return;
    }
    int mid = (l + r)/2;
    
    if(idx <= mid)
    {
        change_s(idx, k, l, mid, 2 * p);
    }
    else
    {
        change_s(idx, k, mid + 1, r, 2 * p + 1);
    }
    
    tree[p] = tree[2 * p] + tree[2 * p + 1];
}


单点修改的时间复杂度也为 .

区间修改、懒标记

接下来是线段树的重头戏：区间修改。显然，不可能通过一个个的单点修改来实现区间修改，这样时间效率还不如直接暴力修改。

区间修改的操作与之前的区间查询很相似，都是找到若干的区间能组成寻找区间

这里先引入一个新的概念：

懒标记

直接看栗子，我们现在想把数组中 [1,4] 中所有的数修改为 16

那么，我们通过递归找到了需要的节点（下图粉红色带圆圈的节点）

这时，我们知道，这个节点的值应该被修改为 64 （16*4=64）（16乘区间长度）。

这时，我们不需要继续往下递归，而是给这个节点打上一个标记。我们可以把这个标记设为16，意为这个区间的数已经被修改为16，如图所示：

然后回溯的过程中再更新结点的值：

从作用可以体会到为什么叫懒标记（就像别人给你家长一些钱说是给你和弟弟的压岁钱，然后家长就说先不给你们，等需要用的时候再给你们）

现在，我们再进行下一次修改，要将 [3, 8] 区间内的数修改为 7：

还是一样的操作，先找到需要的节点，但是，我们在找所需节点时遇到了带标记的节点（刚刚的区间修改操作打的标记），这时，我们把标记下传：

下传完毕后，继续查找，访问节点 [3,4] :

找到这些节点后，也是像刚刚一样，修改节点的值，并打标记。

注意：这里代表区间 [3,4] 的节点原来标记为 16 ，意为该区间已经被修改为16，现在我们想把这个区间更改为7，直接将标记修改即可。

我们想将 [3, 8] 区间内的数修改为 7 :

[3,4] 区间长度为2，所以节点值应改为 7 * 2 = 14，标记为 7；

[5,8] 区间长度为4，所以节点值应改为 7 * 4 = 28，标记为 7；

别忘记回溯时修改沿途节点：

在这里我猜可能有人会有疑惑：为什么加了标记以后就能保证区间修改时间复杂度为 .

其实很简单：很显然区间修改时遍历过的节点数（浅蓝色+粉红色）与区间查询时遍历的节点是一样的；那么，只有这 个节点需要下传标记，所以区间修改时间复杂度为   .

代码如下，当然，加入了懒标记后，之前说到的几个操作都有少许的变动，这里先给出区间修改的代码再将全部操作代码一起给出：

全部代码

线段树节点的构造

struct seg{    int val, tag;    bool have_tag;}tree[400010]; //线段树数组

int arr[100010]; // 原数组

下传标记的函数

void push_tag_down(int p, int l, int r)
{
    if(tree[p].hava_tag)
    { //如果当前结点的标记不为 0 ，将当前结点的标记下传
        int mid = (l + r) / 2;
        seg root = tree[p], ls = tree[2 * p], rs = tree[2 * p + 1];
        //结点值为 标记值 * 区间长度
        ls.val = root.tag * (mid -l + 1);
        ls.tag = root.tag, ls.have_tag = true;
        rs.val = root.tag * (r - mid);
        rs.tag = root.tag, rs.hava_tag = true;
        
        root.hava_tag = false;
    }
}


区间修改的函数

void change(int nl, int nr, int k, int l, int r, int p = 1){// k为区间[l, r]内每个数的变化量   if(nl <=l && r <= nr)   { // 当该节点的区间是访问区间的子集       tree[p].val = (r - l + 1) * k;       tree[p].tag = k;       tree[p].hava_tag = true;       return;   }   push_tag_down(p, l, r); //访问到带标记的结点就下传标记

   int mid = (l + r) / 2;   if(nl <= mid) // 与左子区间相交   {       change(nl, nr, k, l, mid, 2 * p);   }   if(nr > mid)   {       change(nl, nr, k, mid + 1, r, 2 * p + 1);   }

   tree[p].val = tree[2 * p].val + tree[2 * p + 1].val;//回溯时更新}

加入懒标记后的建树函数

void build(int l, int r, int p = 1)
{//建立线段树，[l, r]为节点代表的范围 p 为节点在线段树数组下标
    tree[p].tag = 0;
    tree[p].hava_tag = false;
    
    if(l == r)
    {
        tree[p].val = arr[l];
        return;
    }
    int mid = (l - r)/2 ;
    build(l, mid, 2 * p); // 递归处理左子区间
    build(mid + 1, r, 2 * p + 1); //递归处理右子区间
    
    tree[p].val = tree[2 * p].val + tree[2 * p + 1].val; //合并左右子区间的信息
}


加入懒标记后的查询函数

注意，查询函数中同样需要下放标记！

int query(int nl, int nr, int l, int r, int p = 1){//[nl, nr]为所访问区间， [l, r]为当前节点代表的区间    if(nl <= l && r <= nr) // 当该节点的区间是访问区间的子集    {        return tree[p].val;    }

    push_tag_down(p, l, r); // 访问到就下传标记

    int mid = (l + r) / 2;    int sum = 0;    if(l <= mid) //与左子区间相交    {        sum += query(nl, nr, l, mid, 2 * p);    }    if(r > mid) // 与右子区间相交    {        sum += query(nl, nr, mid + 1, r, 2 * p + 1);    }

    return sum;}

注：这里没有单点修改的代码

因为单点修改可以通过调用区间修改函数来修改一个长度为1的区间来实现。且纯单点修改的代码跟区间修改的几乎相同（懒）。

主函数中的调用

int main()
{
    int n, m, opt, l, r, k;
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    build(1, n);
    for(int i = 1; i <= m; i++)
    {
        cin>>opt>>l>>r;
        if(opt==1)
        {
            cin>>k;
            change(l,r,k,1,n);
        }
        else{
            cout<<query(l,r,1,n);
        }
    }
    return 0;
}


区间合并操作与懒标记的运用

介绍完3个主要操作，线段树的主体已经介绍完了，大家不要被这100多行的代码吓到，我这里是为了打注释留了很多空位，大家实际打的过程中每个函数只有15行左右！

接下来是一些小的进阶。

通过上面的几个操作，相信大家已经发现了线段树的核心：

通过对小区间信息的合并来得到大区间的信息，查询时将几个区间合并即可得到指定区间的信息。

同时，对懒标记的巧妙运用可以对很多信息进行维护，此处给出几个例题，熟悉线段树的使用

基础：

https://www.luogu.com.cn/problem/P3372（例题的变形）

https://www.luogu.com.cn/problem/P3373（懒标记的使用）

进阶：

https://www.luogu.com.cn/problem/P6242

对于区间信息合并的进一步讨论

对于例题而言，合并两信息只需要把两个子区间得到的数相加就可以了，但是实际情况中不可能只让我们求出一堆数的和，比如下面这道题：

https://www.luogu.com.cn/problem/P4198

这个就留作思考题啦，这里不作展开（我也是看了题解才会的qwq）

权值线段树

顾名思义，权值线段树就是统计权值的线段树！

上一道简单的例题

相信接触过平衡树的同学直接就看出来了：这不就是平衡树的模板题嘛

但是在考场上写动不动就一两百行的平衡树未免太折磨人了！

下面来介绍权值线段树的写法

在一开始的例题中，线段树一个节点记录的是这个节点对应的区间的数的和。在权值树里，节点记录的则是对应区间的数出现了几次！

例如，对于集合 [1,3,3,5,4,8] 权值线段树的结构为这样：

节点记录的是节点所代表的区间的数的出现次数，比如 [1,3,3,5,4,8]  2 中 1 出现 1次，2、6 和 7 出现 0 次，3 出现 2 次 ， 4 出现 1 次，5 出现 1 次，8 出现 1 次，所以叶子结点中表示的就是对应数组出现次数，其他结点代表区间内所包含数的出现次数。

那么，题目中的插入的数的值域可是有 啊，怎么能开下这么多的空间?

所以，在这里不能使用堆式建树

动态开点

从上面的图里可以看出有一些点是不需要用到的

夸张一点：

这些黑色节点我们一开始不需要，等到需要用到的时候再开辟就可以了！

这里我先介绍竞赛中比较常见的，较为容易的实现方法：

我们可以声明一个足够大的线段树数组，再声明一个变量 cnt（记录用过的节点数），当我们访问到一个没访问过的节点时，令 cnt++，则线段树数组中下标为 cnt 的节点即为新节点，只需要想办法让新节点跟以前的节点联系上就好了

struct seg {    int ls, rs, val;    seg(int v=0,int l=0, int r=0):val(v),ls(l),rs(r){};};seg t[MAX_N];int cnt;

inline void pushup(int o){    t[o].val = t[t[o].ls].val + t[t[o].rs].val;}

void change(int &o, int l, int r, int k, int v){    // 将 k 的出现次数改变 v，[l, r]为当前节点代表的区间    if(!o) o = ++cnt;    if(l == r)    {        t[o].val += v;        return;    }    int mid = (l + r) / 2;    if(k <= mid) change(t[o].ls, l, mid, k, v);    else change(t[o].rs, mid + 1, r, k, v);    pushup(o);}

这里的change 函数与前面的逻辑一致，除了这句话

if(!o) o = ++cnt;

而且这里的 o 是以引用的方式传进来的，其实这里的o就是节点在线段树数组中的下标

回顾代码，在线段树数组被声明时，每一个节点的左右子节点都为0，那么，我们在递归的过程中遇到了 o 为零，就可以确定这个节点未被使用。

而以引用的方式传入，则可确保原值被赋值，即 t[o].ls 和 t[o].rs 。

即实现了将新开辟的节点与其父节点相联系，理解了change函数，插入与删除操作就很简单了

如果要插入 x ，则执行 change ( 1 , -1e9 , 1e9 , x , 1 )

如果要删除 x，则执行 change ( 1 , -1e9 , 1e9 , x , -1 )

设区间长度为 n，则线段树的树高是 ，在这里区间长度即是值域的大小 ，每次操作最多产生新节点数即是 ，30个左右，所以空间是绝对足够的。

如果想要追求效率的话，可以用离线算法，将所有询问到的数记录下来并离散化，再使用权值线段树，感兴趣的话可以自己实现一下，接下来的操作如果理解了一开始的线段树的介绍后就是很简单的了！

查找排名第k的数

访问到一个节点时，记录左子区间的数的次数为 num，如果 k <= num，则向左子节点递归；否则，将k减去num，再向右子节点递归 。

int query_kth(int o, int l, int r, int k)
{
    if(l == r){
        return l;
    }
    int mid = (l + r)/2;
    int num = t[t[o].ls].val;
    if(k <= num)
    {
        return query_kth(t[o].ls, l, mid, k);
    }
    else
    {
        return query_kth(t[o].rs, mid + 1, r, k - num);
    }
}


为什么向右子节点递归时k要减去 num ?

这个函数其实是求以 o 为根的树中第 k 的数，又 num 代表的是左子区间的数的次数，那么右子区间的第 k-num 的数就是以 o 为根的子树的第 k 的数了 .

查询数 k 的排名

设当前节点代表的区间的中点为 mid ，当 k <= mid 时，向左子节点递归；否则，设左子区间的数的次数为num，向右子节点递归，再将得到的数加上 num 并返回 。

int query_rk(int o, int l, int r, int k){    if(l == r){        return 1;    }    int mid = (l + r)/2;    if(k <= mid)    {        return query_rk(t[o].ls, l, mid, k);    }    else    {        return t[t[o].ls].val + query_rk(t[o].rs, mid+1, r, k);    }}

查询前驱和后继的操作很简单，这里就留作作业啦! 一开始时说到，这是竞赛时可用的，较为简短的版本!

对于动态开点，vector、指针，都是可行的方法；用指针的话，可以避免类似 t[t[o].ls].val 这种写法，但是也会带来较大的调试难度！这里就不作更多的展开了，大家可以自己尝试不同的写法！

写在结尾：

本来的计划最后面还有zkw线段树，和可持久化的介绍，但是突然发现已在 word 中写了 20 多页。。。

那么本文就先这样结束啦，如果我讲解的有些地方不太周全欢迎大家指点，如果喜欢这个文章的话欢迎点个赞啦嘻嘻~~