什么是线段树？

文章目录

什么是线段树？一、简介二、线段树的结构与建树如何存储这个线段树呢? 三、区间查询那么如何判断两个区间是否有交集？ 四、单点修改五、区间修改、懒标记懒标记 六、完整代码线段树节点的构造下传标记的函数区间修改的函数加入懒标记后的建树函数加入懒标记后的查询函数主函数中的调用 七、区间合并操作与懒标记的运用八、权值线段树动态开点 九、查找排名第k的数十、查询数 k 的排名

一、简介

线段树是在算法竞赛中常用来维护区间信息的数据结构，同时，线段树的理解难度较树状数组低（当然是在理解递归的前提下）。 线段树可以在 $O(logN)$ 的时间复杂度内实现对数组的单点修改、区间修改、区间查询等操作。 下面以一个简单的例题进行介绍：给定一个数组 arr[0 … n-1]，执行不超过10万次以下两个操作：1、输出数组中 [left, right] 区间内的数的和，也就是 a[left] + a[left+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 ] 执行上面提到的递归划分过程后：

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

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

如何存储这个线段树呢?

最简单的方法是堆式建树即像下面这样，我们可以用一个数组直接存储线段树的节点，节点在数组中下标如图：

由图，我们可以发现一个规律：对于一个节点，设其在数组中下标为 $p$ ，则该节点的左子节点的下标为 $2\ast p$ ，右子节点的下标为 $2\ast p+1$ ，父节点的下标为 $p/2$ (取下界)。 建树的代码： int arr[100010];//原数组 int tree[400010]; //线段树数组 //建立线段树，[l, r]为节点代表的范围， p 为节点在线段树数组的下标 void build(int left, int right, int p = 1) { //区间长度为 1， 节点值即为原数组对应位置的值； if(left == right) { 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倍

三、区间查询

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

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

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

查询区间 [1, 5] :

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

查询区间 [3, 6]：

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

查询区间 [5, 6] :

查询区间的数的和即是 $9$

查询区间 [1, 7] :

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

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

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

为了查找这些浅蓝色节点，从根向下遍历，每遇到一个节点，可分为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 ，所以查询区间与当前结点区间为右子区间相交。

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

//[nl, nr]为所访问区间，[l, r]为当前结点代表的区间 int query(int nl, int nr, int l, int r, int p = 1) { //代表当前节点代表的区间为查询区间的子集 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:

实现代码超级简单（这就是递归的魅力，代码简洁）： // 将arr[idx] 的值修改为 k, [l, r] 为当前结点代表的区间 void change_s(int idx, int k, int l, int r, int p = 1) { //代表找到idx的节点 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]; } 单点修改的时间复杂度也为 $O(logN)$

五、区间修改、懒标记

接下来是线段树的重头戏：区间修改。显然，不可能通过一个个的单点修改来实现区间修改，这样时间效率还不如直接暴力修改。区间修改的操作与之前的区间查询很相似，都是找到若干的区间能组成寻找区间

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

懒标记

直接看栗子，我们现在想把数组中 [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；

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

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

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

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

六、完整代码

线段树节点的构造

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

下传标记的函数

void push_tag_down(int p, int l, int r) { //如果当前结点的标记不为 0 ，将当前结点的标记下传 if(tree[p].hava_tag) { 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; } }

区间修改的函数

// k为区间[l, r]内每个数的变化量 void change(int nl, int nr, int k, int l, int r, int p = 1) { // 当该节点的区间是访问区间的子集 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;//回溯时更新 }

加入懒标记后的建树函数

//建立线段树，[l, r]为节点代表的范围 p 为节点在线段树数组下标 void build(int l, int r, int p = 1) { 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; //合并左右子区间的信息 }

加入懒标记后的查询函数

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

//[nl, nr]为所访问区间， [l, r]为当前节点代表的区间 int query(int nl, int nr, int l, int r, int p = 1) { 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; }

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

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

八、权值线段树

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

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

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

在一开始的例题中，线段树一个节点记录的是这个节点对应的区间的数的和。在权值树里，节点记录的则是对应区间的数出现了几次！例如，对于集合 [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 次所以叶子结点中表示的就是对应数组出现次数，其他结点代表区间内所包含数的出现次数。那么，题目中的插入的数的值域可是有 $10^9$ 啊，怎么能开下这么多的空间?所以，在这里不能使用堆式建树

动态开点

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

夸张一点：

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

这里我先介绍竞赛中比较常见的，较为容易的实现方法：我们可以声明一个足够大的线段树数组，再声明一个变量 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，则线段树的树高是 $logN$ ，在这里区间长度即是值域的大小$2^9$ ，每次操作最多产生新节点数即是 $log(2^9)$ ，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 这种写法，但是也会带来较大的调试难度！这里就不作更多的展开了，大家可以自己尝试不同的写法！