线段树的扩展之浅谈zkw线段树

点击前往[我的blog](https://blog.tifa-233.com/archives/zkw-segment-tree/)获取更好阅读体验 # 0 阅读本文前请先阅读： - [【洛谷日报#4】浅谈线段树（Segment Tree）](https://pks-loving.blog.luogu.org/senior-data-structure-qian-tan-xian-duan-shu-segment-tree) 本文主要是上面文章的延伸，所以上文有讲的东西本文就不详细讲了QwQ 笔者的测试代码可能写丑了，所以如果慢请自行卡常QwQ #### 这里还是以**区间求和(RSQ)**为例 # 1 zkw线段树简介 什么是zkw线段树？ 简单来说，就是**非递归式**线段树 众所周知，递归式线段树的常数很大，经常被卡，而zkw线段树的常数很小 这里用[洛谷P3372](https://www.luogu.org/problemnew/show/P3372)做一个演示（更详细的补充见文末） **递归式线段树**[R9389075](https://www.luogu.org/record/show?rid=9389075)  **zkw线段树**[R9388963](https://www.luogu.org/record/show?rid=9388963)  前者运行时间是后者运行时间的**2.05**倍！Σ(°Д°; _测试用代码变量全部是unsigned long long类型的，如果按需调整速度还会更快_ #### 更详细的测试见3 其实zkw线段树不仅快，而且码量小（递归1.8KB，zkw1.48KB）、占用空间小（递归6.31MB，zkw4.94MB）、好调试~~吊打递归式线段树~~orz 而递归式线段树的优点则是方便理解与学习，并且适用范围更广一些（zkw线段树**不能处理有运算优先级的问题**，例如[洛谷P3373](https://www.luogu.org/problemnew/show/P3373)（加法乘法混合处理） ） # 2 zkw线段树的实现 我们观察一下递归式线段树的代码，很容易就会发现：无论是建树、修改还是查询，都是**自顶向下**的。 zkw线段树则正好反过来，即**自底向上** 具体来说，就是先把线段树填充成满二叉树（堆式存储），之后就可以直接找到叶节点，然后回溯上去了 听起来好像很简单QwQ 其实真的很简单QwQ ## 2.1 先来看看怎么建树 首先是定义： ```cpp #define MAXN 200005 int tree[MAXN<<2]; //tree是线段树数组 int n, N=1; //n是原数组实际长度，N下面会解释 ``` 我们以下图为例  (由[visualgo](https://visualgo.net/zh/segmenttree)生成~~为了便于讲解，笔者做了一些改动QwQ~~) 如图，下面的黄圈是原数据，黄圈下面的红色数字是原数组的下标 上面的树就是线段树了，每一个节点内部都是节点下方标明的区间中所有元素的总和，上边的黑色数字就是线段树的下标 ### visualgo生成的数组下标默认是从0开始的，所以线段树下的区间和原数组有错位，请注意区分~~(笔者懒得改了~~ 通过观察，我们发现一个规律：线段树对应叶子节点的下标和原数组的下标的差值是恒定的（$8-1=9-2=...=15-8=7$） 这个差值就是一个和``N``很接近的数了（``N``是叶子节点数） 实际上， $$N=2^{\lceil\log_2{(n+1)}\rceil}$$ 根据这一点，我们可以这样建树： ```cpp #define fp(i,l,r) for(register int i=(l);i<=(r);++i) #define fd(i,r,l) for(register int i=(r);i>=(l);--i) #define il inline //这个根据自己习惯调整，笔者习惯这么写了QwQ il void build() { scanf("%d", &n); for(; N <= n+1; N <<= 1); //这个N当然可以直接算，不过为了算一个数就加一个#include<cmath>有点不划算 fp(i, N+1, N+n) scanf("%d", tree+i); //这个等价于scanf("%d", &tree[i]) fd(i, N-1, 1) tree[i] = tree[i << 1] + tree[i << 1 | 1]; //这个等价于tree[i] = tree[i*2] + tree[i*2 + 1] } ``` 大家可以和递归版线段树做一下对比 有细心的读者可能发现了：上例计算出的``N``是``16``而不是``8``! 还有，原数组在线段树对应的为止整体向后平移了1位！ 其实这都是为了方便查找 后面再详细解释 ## 2.2 接下来需要分成两个版本（单点修改+区间查询 和 区间修改+区间查询） ### 2.2.1 先说说单点修改+区间查询吧(Easy) #### 2.2.1.1 看看单点修改 实现很简单，所以直接放代码 ```cpp il void modify(int x, int k) { for(x += N; x; x >>= 1) tree[x] += k; } ``` 完了？Σ(°Д°; 完了！ 单点查询更简单，相信各位读者都能想到QwQ #### 2.2.1.2 再看看单点修改下的区间查询 我们以查询``[2,6]``为例（线段树上的，下同）  $$ans=\color{#b5e61d}[2,2]+[3,3]+[4,4]+[5,5]+[6,6]$$ 观察上图可以发现，因为在线段树上我们可以直接找到$\color{#00a2e8}[2,3]$和$\color{#00a2e8}[4,5]$，所以我们只需要用$\color{#00a2e8}[2,3]$代替$\color{#b5e61d}[2,2]$和$\color{#b5e61d}[3,3]$;用$\color{#00a2e8}[4,5]$代替$\color{#b5e61d}[4,4]$和$\color{#b5e61d}[5,5]$ 于是 $$ans=\color{#00a2e8}[2,3]+[4,5]\color{#b5e61d}+[6,6]$$ 自顶向下求和很简单，怎么实现自底向上的求和呢？ 我们分别在区间左端点-1和右端点+1的位置放两个指针（令其为``s,t``），就像这样：  接着不断将``s,t``移动到对应节点的父节点处，直到``s,t``指向的节点的父节点相同时停止  在这期间，如果： 1. ``s``指向的节点是左儿子，那么``ans += 右儿子的值`` 1. ``t``指向的节点是右儿子，那么``ans += 左儿子的值`` 如果不能理解就看看上图，多看几遍就懂了QwQ 下面是代码 ```cpp il int query(int s, int t) { int ans = 0; for(s = N + s - 1, r = N + r + 1; s ^ r ^ 1; s >>= 1, r >>= 1) { //这个for包含的信息量好像有点大，不过不要紧 //第一个分号前面就是将s和t初始化 //s ^ r ^ 1就是判断对应节点的父节点是否相同 //很容易看出来当对应节点互为左右儿子时，s^t = 1，再^1之后就是0 //而其他情况时，s^t大于1，^1后当然不是0 //第二个分号后面就是s,t上移 if(~s&1) ans += tree[s^1]; if(r&1) ans += tree[r^1]; //这两句的含义对照上面的实现过程看就能明白 } return ans; } ``` 上面的那两个疑问现在可以解释了 仔细观察上述流程可以发现：我们只能查询``[1,n-1]``范围（这里还是线段树上标的）内的数据 如果我们想要查询``[0,m]``范围内（$0\leq m\leq n$）的呢？ **将数组整体平移！** 如果我们想要查询``[m,n]``范围内（$0\leq m\leq n$）的呢？ **把``N``直接扩大2倍!** ~~_zkw：就是这么狠_~~ ------------------------------- 到目前为止zkw线段树还是比较简短的 可能有人觉得这个和树状数组有点像，这就对了 _zkw：树状数组究竟是什么？就是省掉一半空间后的线段树加上中序遍历_ orz **单点修改+区间查询**完结，整理一下代码： ```cpp //单点修改+区间查询 #include<cstdio> #define MAXN 200005 #define fp(i,l,r) for(register int i=(l);i<=(r);++i) #define fd(i,r,l) for(register int i=(r);i>=(l);--i) #define il inline int tree[MAXN<<2]; int n, N=1; il void build() { scanf("%d", &n); for(; N <= n+1; N <<= 1); fp(i, N+1, N+n) scanf("%d", tree+i); fd(i, N-1, 1) tree[i] = tree[i << 1] + tree[i << 1 | 1]; } il void modify(int x, int k) { for(x += N; x; x >>= 1) tree[x] += k; } il int query(int s, int t) { int ans = 0; for(s = N + s - 1, r = N + r + 1; s ^ r ^ 1; s >>= 1, r >>= 1) { if(~s&1) ans += tree[s^1]; if(r&1) ans += tree[r^1]; } return ans; } int main() { //...自己按需补充吧 } ``` ### 2.2.2 区间修改+区间查询(A little bit hard) #### 2.2.2.1 区间修改——噩梦的开始 很显然，我们不能用上面的方法暴力修改（还不如递归式线段树） 其实堆式存储也可以自顶向下访问 就是上下各走一次而已 但是我们有更好的办法 ~~_zkw:使劲想想就知道了_~~ 这里我们采用**标记永久化**的思想（就是**不下推lazy tag**~~让他彻底lazy下去QwQ~~） ```cpp int add[MAXN<<2]; //这个lazy tag表示当前节点已经更新完，需要更新子节点 ``` 我们需要在自底向上时更新节点的值，所以我们还需要一个变量记录该节点**包含元素的个数** 另外要注意**修改某个节点的标记时要更新上面的值** 举个例子；我们换一棵树  以修改``[2,10]``为例  当``s``到了``[2,2]``节点时，``[3,3]``节点的add加``k``，那么接下来``[2,3]``、``[0,3]``节点的值都要加上``k*1``，而到了``[0,7]``节点时，因为``[4,7]``节点的add加了``k``，所以``[0,7]``节点的值要加上``k*(1+4)=k*5``，自然``k``要乘的系数又需要一个变量来记录 需要注意的是，这次的**修改要上推到根节点** 下面是代码 ```cpp il void update(int s, int t, int k) { int lNum=0, rNum=0, nNum=1; //lNum: s一路走来已经包含了几个数 //rNum: t一路走来已经包含了几个数 //nNum: 本层每个节点包含几个数 for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) { //更新tree tree[s] += k*lNum; tree[t] += k*rNum; //处理add if(~s&1) {add[s^1] += k; tree[s^1] += k*nNum; lNum += nNum;} if(t&1) {add[t^1] += k; tree[t^1] += k*nNum; rNum += nNum;} } //更新上层tree for(; s; s >>= 1, t >>= 1) { tree[s] += k*lNum; tree[t] += k*rNum; } } ``` #### 2.2.2.2 区间查询 我们以查询``[2,10]``为例~~没错笔者我就是用一张图~~  过程类似，要注意``s,t``每次上推时都要根据当前所在节点的标记和``lNum / rNum``更新``ans`` (``ans += add[s]*lNum``) 可能有些难懂，多读两遍或者看看代码或者自己手推一下就好了QwQ 同样，这个也需要上推到根节点 ```cpp il int query(int s, int t){ int lNum=0, rNum=0, nNum=1; int ans=0; for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) { //根据标记更新 if(add[s]) ans += add[s]*lNum; if(add[t]) ans += add[t]*rNum; //常规求和 if(~s&1) {ans += tree[s^1]; lNum += nNum;} if(t&1) {ans += tree[t^1]; rNum += nNum;} } //处理上层标记 for(; s; s >>= 1, t >>= 1) { ans += add[s]*lNum; ans += add[t]*rNum; } return ans; } ``` 区间修改+区间查询到这里先告一段落，整理一下代码： ```cpp //区间修改+区间查询1 #include<cstdio> #define MAXN 200005 #define fp(i,l,r) for(register int i=(l);i<=(r);++i) #define fd(i,r,l) for(register int i=(r);i>=(l);--i) #define il inline int tree[MAXN<<2], add[MAXN<<2]; int n, N=1; il void build() { scanf("%d", &n); for(; N <= n+1; N <<= 1); fp(i, N+1, N+n) scanf("%d", tree+i); fd(i, N-1, 1) tree[i] = tree[i << 1] + tree[i << 1 | 1]; } il void update(int s, int t, int k) { int lNum=0, rNum=0, nNum=1; for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) { tree[s] += k*lNum; tree[t] += k*rNum; if(~s&1) {add[s^1] += k; tree[s^1] += k*nNum; lNum += nNum;} if(t&1) {add[t^1] += k; tree[t^1] += k*nNum; rNum += nNum;} } for(; s; s >>= 1, t >>= 1) { tree[s] += k*lNum; tree[t] += k*rNum; } } il int query(int s, int t){ int lNum=0, rNum=0, nNum=1; int ans=0; for(s = N+s-1, t = N+t+1; s^t^1; s >>= 1, t >>= 1, nNum <<= 1) { if(add[s]) ans += add[s]*lNum; if(add[t]) ans += add[t]*rNum; if(~s&1) {ans += tree[s^1]; lNum += nNum;} if(t&1) {ans += tree[t^1]; rNum += nNum;} } for(; s; s >>= 1, t >>= 1) { ans += add[s]*lNum; ans += add[t]*rNum; } return ans; } int main() { //还是按需编写 } ``` #### 2.2.3 对区间修改+区间查询进行空间优化(A Little hard) 也许有的读者发现了：标记和值好像可以看成一个东西 所以，我们可不可以**不存值，只存标记**？ **当然可以！** _**zkw：永久化的标记就是值!**_ _~~zkw：狗拿耗子，猫下岗了~~_ 那么，怎么实现呢？ #### 下面是**区间最值(RMQ)版本**的（以最小值为例） > 在这里，我们不存总和了，存``tree[i]=sum[i]-sum[i>>1] //sum[i]对应上述两个版本代码中的tree[i]``(即为子节点-父节点) > > 区间修改就直接改``tree[i]`` > > 查询就从当前节点一直加到根(``tree[i]+tree[i>>1]+...+tree[1]``) 或者数学一点 $$\displaystyle\sum_{\text{j}=0}^{\lfloor\log_2\text{i}\rfloor}\text{tree[i>>j]}$$ > （修改时的``s,t``）遇到节点``x``，则 > > ``A=min(tree[x>>1],tree[x>>1|1]), tree[x]+=A, tree[x>>1]-=A, tree[x>>1|1]-=A `` > ``//这一步可能有一些难懂，就是修改了一个区间，可能会导致父节点存储的最值（普通情况下）发生改变，所以用这一步来修正`` 为什么笔者没有放**区间求和(RSQ)版本**的呢？ 因为笔者发现区间求和版本的依然要维护两棵树（一棵存``tree[i]-tree[i-1]``，另一棵存``i*(tree[i]-tree[i-1])``，类似树状数组），也就是没有优化（可能是笔者太弱了，没有想到别的方法） 当然，这个版本也是可以单点修改/单点查询的，不过没有上述代码实用，所以这里就不讨论了 直接放代码 ```cpp void build() { for(N=1;N<=n+1;N<<=1); fp(i,N+1,N+n) scanf("%d",tree+i); fd(i,N-1,1) { tree[i]=min(tree[i<<1],tree[i<<1|1]); tree[i<<1]-=tree[i]; tree[i<<1|1]-=tree[i]; } } void update(int s, int t, int k) { int tmp; for(s += N-1, t += N+1; s^t^1; s>>=1, t>>=1) { if(~s&1) tree[s^1]+=k; if(t&1) tree[t^1]+=k; tmp = min(tree[s], tree[s^1]); tree[s] -= tmp; tree[s^1] -= tmp; tree[s>>1] += tmp; tmp = min(tree[t], tree[t^1]); tree[t] -= tmp; tree[t^1] -= tmp; tree[t>>1] += tmp; } for (;s!=1;s>>=1) { //记得要上推到根节点 tmp = min(tree[s],tree[s^1]); tree[s] -= tmp; tree[s^1] -= tmp; tree[s>>1] += tmp; } } int query(int s, int t) { //闭区间 int sAns = 0, tAns = 0; s+=N, t+=N; if(s != t) { //防止查询单点时死循环 for(; s^t^1; s>>=1, t>>=1) { sAns += tree[s]; tAns += tree[t]; if(~s&1) sAns = min(sAns, tree[s^1]); if(t&1) tAns = min(tAns, tree[t^1]); } } int ans = min(sAns+tree[s], tAns+tree[t]); while(s > 1) ans += tree[s>>=1]; return ans; } ``` # 3 大数据测试 当然，说好的大数据测试可不能忘 **(2020.02.10 upd: [测试更新了](https://www.luogu.com.cn/blog/82152/test-of-zkwSegTree))** 先来看一看参赛选手： 1号：递归线段树 2号：zkw线段树（非差分版本，差分版本的常数略大，就不测了） 3号：树状数组 ~~zkw线段树：说好的我的主场呢？~~ 先以[洛谷P3372](https://www.luogu.org/problemnew/show/P3372)做一个热身 因为图太多，所以不贴出来了，有兴趣的读者可以查看提交记录 **读入优化** 1号：递归线段树 412ms / 6.31MB ([R9424058](https://www.luogu.org/record/show?rid=9424058)) 2号：zkw线段树 208ms / 4.74MB ([R9424567](https://www.luogu.org/record/show?rid=9424567)) 3号：树状数组 196ms / 3.71MB ([R9424624](https://www.luogu.org/record/show?rid=9424624)) **读入优化+O2** 1号：递归线段树 220ms / 6.21MB ([R9424921](https://www.luogu.org/record/show?rid=9424921)) 2号：zkw线段树 160ms / 4.86MB ([R9424805](https://www.luogu.org/record/show?rid=9424805)) 3号：树状数组 96ms / 3.74MB ([R9424762](https://www.luogu.org/record/show?rid=9424762)) 可以看到，没有O2时2号和3号相差无几，有了O2之后3号吊打全场~~可能是笔者写的zkw线段树常数太大QwQ~~ 为了~~防止zkw线段树被吊打得太惨~~反应算法真实水平以及模拟NOIp竞赛环境，下面就不开O2了 在这里先放一下结果，测试代码和大数据放在[另一篇文章](https://www.luogu.com.cn/blog/82152/TestData-and-Code-of-the-text-Introduction-of-zkwSegmentTree)里 保证所有输入数据在unsigned long long 范围内，结果对$2^{64}$取模，表格中的时间为平均值 测试环境： 系统：noilinux-1.4.1（当然是虚拟机啦） 内存：2GB CPU：AMD Athlon(tm) II X4 631 Quad-Core Processor 2600 MHz（就用了一个核） 请不要吐槽这个渣配置QwQ~~(话说这个配置和CCF老爷机的配置应该差不多吧)~~ ~~顺便吐槽那个系统自带的辣鸡评测软件，一评测就闪退~~ ##### 测试#1： | 数据规模 | 递归线段树(ms) | zkw线段树(ms) | 树状数组(ms) | | :----------: | :----------: | :----------: | :----------: | | 5e5(5组) | 3554.359 | 2067.978 | 1968.074 | | 1e6(5组) | 7327.344 | 4922.725 | 4359.272 | | 5e6(3组) | 49416.196 | 34078.837 | 26782.107 | | 1e7(3组) | 126192.820 | 74198.015 | 57485.430 | ##### 测试#2（稍微卡卡常）： | 数据规模 | 递归线段树(ms) | zkw线段树(ms) | 树状数组(ms) | | :----------: | :----------: | :----------: | :----------: | | 5e5(5组) | 3985.435 | 2085.221 | 1981.154 | | 1e6(5组) | 6995.611 | 4268.988 | 3991.724 | | 5e6(3组) | 45401.981 | 29582.957 | 25179.336 | | 1e7(3组) | 99805.488 | 67543.985 | 54304.283 | 耗时：$\text{树状数组}\thickapprox\text{zkw线段树}<\text{递归线段树}$ 代码长度：$\text{树状数组(1.57 KB)}<\text{zkw线段树(2.20 KB)}<\text{递归线段树(2.47 KB)}$ （当然这个参考意义不大） 结论：**不考虑有运算优先级的情况**下，树状数组吊打全场（zkw线段树哭晕在厕所 # 4 后记 这篇文章笔者写了~~将近一天~~整整三天。通过写这篇文章，笔者对zkw线段树的理解更加深刻了~~顺便还学到了差分这个骚操作，并让树状数组吊打全场~~ 当然，因为笔者是个蒟蒻，所以这篇文章难免会有错误，在此希望各位dalao批评的时候别把笔者喷得太惨QwQ 另外，zkw julao在他的ppt中还讲了许多高端操作，希望各位有兴趣读者能够看一看~~膜拜orz~~ 关于线段树，还可以扩展出很多东西，比如多维线段树、多叉线段树、可持久化线段树……不过因为笔者是个蒟蒻，所以这些就先不写了 # 5 主要参考资料 - [统计的力量——线段树全接触](https://artofproblemsolving.com/community/c1368h1020439)~~(膜拜zkw julao)~~ - [线段树详解 （原理，实现与应用） - CSDN博客](https://blog.csdn.net/zearot/article/details/48299459)