zkw 线段树-原理及其扩展

Tmbcan · 2024-10-10 10:37:04 · 算法·理论

前言

许多算法的本质是统计。线段树用于统计，是沟通原数组与前缀和的桥梁。

《统计的力量》清华大学-张昆玮

更好的阅读体验

Update 2025.8.13：准备从今天开始陆续整理一下文章，早年写的一些东西过于抽象了。

Update 2025.9.15：早年我真的写了这么多抽象东西吗？好多修也不好修了，就当是成长历程了。文章大家凑活着看吧，有啥问题私下喷飞我即可。

Update 2026.6.24：增加了一些内容。

关于线段树

前置知识：线段树 OIWiki。

线段树是一种专门维护区间问题的数据结构。
线段树对信息进行二进制化处理并在树形结构上维护，以此让处理速度达到 O(\log{n}) 级别。

线段树的实现方式

由于线段树的树形结构特点，每次修改查询可以从根节点向下二分查找需要用到的节点，因此较为普遍且快捷的线段树会使用递归实现。

但递归实现的线段树由于每次要从根节点递归向下传递子树信息，导致常数较大，容易被卡常，所以出现了常数更小的递推实现的线段树（膜拜 zkw 大佬）。

zkw 线段树

先来讲一些小原理。

一、原理

由于递归实现的线段树不是一棵满二叉树，其叶子节点位置不确定，导致每次操作都需要从根节点开始自上而下递归依次寻找叶子节点，回溯时进行维护，递归过程常数就比较大了。

所以 zkw 线段树就直接建出一棵满二叉树，原序列信息都维护在最底层。严格规定父子节点关系，同层节点的子树大小相等。
这样每个叶子节点都可以直接找到并修改，由于二叉树父子节点的二进制关系，就可以递推直接找到对应节点的父亲节点自下而上地维护节点关系。

二、初始化

1、建树

对长度为 n 的序列建一棵 zkw 线段树，其至少有 n+2 个叶子节点。其中有 2 个用来帮助维护区间信息的虚点，有 n 个用来存原序列信息的节点。
如图（【模板】线段树 1 的样例为例，下同）：

建树时先求出虚点 P 位置，然后直接向其他叶子节点读入信息即可:

//先求虚点 P
  P = 1;
  while(P<=n+1) P<<=1;//节点深度每增加一层，当前层节点数量扩大一倍
  for(int i=1;i<=n;++i) read(tr[P+i]);

2、维护

根据上文所说，由于严格确定了父子关系，所以直接自下而上遍历所有节点维护父子关系做初始化：

//push_up
  for(int i=P-1;i;--i){//i=(P+n)>>1
    tr[i] = tr[i<<1|1]+tr[i<<1]; 
    tr[i] = min(tr[i<<1|1],tr[i<<1]);
    tr[i] = max(tr[i<<1|1],tr[i<<1]);
    //...
  }

三、概念介绍

1、永久化懒标记

与递归线段树的 lazy tag 不同，其每次向下递归时都需要先下放标记并清空以维护信息。

但在维护存在结合律的运算时，zkw 线段树的 lazy tag 只会累加，而不会在修改和查询前下放清空。

2、“哨兵”节点

在区间操作时，引入两个哨兵节点，分别在区间的左右两侧，把闭区间变成开区间进行处理。

两个哨兵节点到根有两条链，与两条链相邻且在中间部分的节点，就是这次操作需要用到其信息的所有节点。

如图（沿用了第一个图，节点中的数的为节点编号）：
例如：【模板】线段树 1 第一个操作 query(2,4)：

同时，这也解释了为什么建树时叶子节点上会有 2 个虚点。

（1）为什么可以确定需要用到哪些节点

操作时，只需要操作区间中单元素区间的公共祖先即可。
我们选取的两条链，中间部分正好包含了与操作区间有关的所有节点，与两条链相邻的节点显然的所有区间的公共祖先。

操作时只需要操作这些节点上的信息就可以了。

（2）在递推过程中怎么判断要用到哪些节点

观察我们刚才手推出来的图片，注意到：
对于左哨兵 S，当它是左儿子时，其兄弟节点是需要用到的；
对于右哨兵 T，当它是右儿子时，其兄弟节点是需要用到的。

每次操作完后 S 和 T 向上走到自己的父亲节点，然后维护父子关系，再进行新一轮操作。
当 S 和 T 互为兄弟节点时（走到了两条链的交点），就停止操作，然后向上维护信息到根节点。

四、基于结合律的查询与修改

1、区间修改

以区间加为例。
类似递归线段树操作，更新时需要知道当前节点的子树大小。
每次更新时，当前节点的值增加的是其标记乘子树大小；其标记的值正常累加即可。
永久化懒标记减少了标记下放带来的常数。

//
  inline void update_add(int l,int r,ll k){
    l=P+l-1; r=P+r+1;//哨兵位置 
    int siz = 1;//记录当前子树大小 

    while(l^1^r){//当l与r互为兄弟时，只有最后一位不同 
        if(~l&1) tr[l^1]+=siz*k,sum[l^1]+=k;
        if(r&1) tr[r^1]+=siz*k,sum[r^1]+=k;
        //类似递归线段树 tr[p] += tag[p]*(r-l+1) 
        l>>=1; r>>=1; siz<<=1;
        //每次向上走时子树大小都会增加一倍 
        tr[l] = tr[l<<1]+tr[l<<1|1]+sum[l]*siz;//维护父子关系 
        tr[r] = tr[r<<1]+tr[r<<1|1]+sum[r]*siz;
    }
    for(l>>=1,siz<<=1;l;l>>=1,siz<<=1) tr[l] = tr[l<<1]+tr[l<<1|1]+sum[l]*siz;//更新上传至根节点
  } 

2、区间查询

由于我们需要查询的区间被左右哨兵分为了两个部分，但两部分子树大小不一定相等。
所以要分别维护左右哨兵到达的节点所包含查询区间的子树的大小。

//
  inline ll query_sum(int l,int r){
    l=l+P-1; r=r+P+1;
    ll res = 0;
    int sizl = 0,sizr = 0,siz = 1;//分别维护左右两侧子树大小

    while(l^1^r){
        if(~l&1) res+=tr[l^1],sizl+=siz;//更新答案及子树大小 
        if(r&1) res+=tr[r^1],sizr+=siz;
        l>>=1; r>>=1; siz<<=1;

        res += sum[l]*sizl+sum[r]*sizr;
        //即使当前节点所存的区间和不需要用，但因为其是两个哨兵的父亲节点，且 tag 不会下传，
        //所以其 tag 会对答案有贡献，所以需要加上 tag 的贡献
    }
    for(l>>=1,sizl+=sizr;l;l>>=1) res+=sum[l]*sizl;//累加至根节点 
    return res;
  }

如果维护区间最大值也同理：

//
  inline void update_add(int l,int r,ll k){
    l=P+l-1; r=P+r+1;
    while(l^1^r){
        if(~l&1) sum[l^1]+=k,maxn[l^1]+=d;
        if(r&1) sum[r^1]+=k,maxn[r^1]+=d;
        l>>=1; r>>=1;
        maxn[l] = max(maxn[l<<1],maxn[l<<1|1])+sum[l];
        maxn[r] = max(maxn[r<<1],maxn[r<<1|1])+sum[r];
    }
    for(l>>=1;l;l>>=1) maxn[l]=max(maxn[l<<1],maxn[l<<1|1])+sum[l];//更新上传至根节点
  } 
  inline ll query_max(int l,int r){
    l=l+P-1; r=r+P+1;
    ll resl = 0,resr = 0;//分别记录左右两侧最大值 
    while(l^1^r){
        if(~l&1) resl=max(resl,maxn[l^1]);
        if(r&1) resr=max(resr,maxn[r^1]);
        l>>=1; r>>=1;
        resl += sum[l];//标记永久化，所以要累加标记值
        resr += sum[r];
    }
    for(resl=max(resl,resr),l>>=1;l;l>>=1) res1+=sum[l];//累加至根节点
    return resl;
  }

某些时候，只会用到单点修改区间查询和区间修改单点查询，此时 zkw 线段树码量优势很大。

3、单点修改下的区间查询

修改：直接改叶子结点的值然后向上维护。
查询：哨兵向上走时直接累加节点值。

//
  inline update(int x,ll k){
    x += P; tr[x] = k;
    for(x>>=1; x ;x>>=1) tr[x] = tr[x<<1]+tr[x<<1|1]; 
  }
  inline ll query(int l,int r){
    l += P-1; r += P+1;
    ll res = 0;
    while(l^1^r){
        if(~l&1) res+=tr[l^1];
        if(r&1) res+=tr[r^1];
        l>>=1; r>>=1;
    }
    return res;
  }

4、区间修改下的单点查询

将赋初值的过程看作是在叶子节点上打标记，区间修改也是在节点上打标记。
由于 zkw 线段树的标记是永久化的，所以此时将标记的值看作节点的真实值。
但这种做法显然只对于单点查询有效，在查询时需要加上节点到根沿途的所有标记。

//
  inline void update_add(int l,int r,ll k){
    l += P-1; r += P+1;
    while(l^1^r){
        if(~l&1) tr[l^1]+=k;
        if(r&1) tr[r^1]+=k;
        l>>=1; r>>=1;
    }
  }
  inline ll query(int x){
    ll res = 0;
    for(x+=P; x ;x>>=1) res+=tr[x];
    return res;
  }

5、标记永久化的局限性

以上修改与查询方式，全部基于运算具有结合律，所以标记可以永久化，以此减少标记下放增加的常数。

但如果运算存在优先级，标记就不能再永久化了。考虑在更新时将先标记下放（类似递归线段树）然后再从叶子节点向上更新。

但是如果像递归线段树一样从根开始逐次寻找子节点下放一遍的话，那优化等于没有。
所以要考虑基于 zkw 线段树的特点进行下放操作，而且要尽可能的简洁方便。

So easy，搜一紫衣。

五、有运算优先级的修改与查询

1、标记去永久化

在进行区间修改时，我们会用到的节点只存在于哨兵节点到根的链上。
所以只考虑将这两条链上的节点标记进行下放即可。

（1）如何得到有哪些需要下放标记的节点

考虑最暴力的方法：
每次从哨兵节点向上递归直至根节点，回溯时下放标记。
显然这样的方式常数优化约等于零。

考虑优化肯定是基于 zkw 线段树的特点。
还是由于 zkw 线段树是满二叉树结构，所以可以通过节点编号移位的方式找到其所有父子节点的编号。
显然哨兵到根节点的链，是哨兵的所有父亲组成的，所以只要让哨兵编号移位就可以了。

（2）如何自上而下的传递标记

再记录一下叶子节点的深度。
思考满二叉树的性质：当节点编号右移位节点深度时就指向根节点编号。
所以节点右移的位数，从节点深度依次递减，就可以自上而下得到其所有父亲节点的编号。

2、区间修改

先下放标记，然后正常做标记更新。
传递标记时可能要考虑子树大小，直接通过深度计算就可以了。
以区间加及乘为例：

//建树时记录叶子节点深度 
  P = 1;DEP = 0;
  while(P<=n+1) P<<=1,++DEP;
  //...
  //...
  //...
  inline void update_add(int l,int r,ll k){
    l=P+l-1; r=P+r+1;
    //先下放标记 
    for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i); 
    //push_dwon( 链上节点 , 当前子树大小 );

    int siz = 1;
    while(l^1^r){
        if(~l&1) tr[l^1]+=siz*k,sum[l^1]+=k;//正常更新
        if(r&1) tr[r^1]+=siz*k,sum[r^1]+=k;
        l>>=1; r>>=1; siz<<=1;

        //维护父子关系 
        tr[l] = tr[l<<1]+tr[l<<1|1];//由于标记已下放，所以维护时不再考虑累加标记 
        tr[r] = tr[r<<1]+tr[r<<1|1];
    }
    for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];//上传至根节点 
  }
  //
  inline void update_mul(int l,int r,ll k){
    l += P-1; r += P+1;
    for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i);
    while(l^1^r){
        if(~l&1) tr[l^1]*=k,mul[l^1]*=k,sum[l^1]*=k;//标记覆盖
        if(r&1) tr[r^1]*=k,mul[r^1]*=k,sum[r^1]*=k;
        l>>=1; r>>=1;
        tr[l] = tr[l<<1]+tr[l<<1|1];
        tr[r] = tr[r<<1]+tr[r<<1|1];
    }
    for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
  }

3、区间查询

先下放标记。
由于标记已经去永久化，所以直接累加节点值即可。

//
  inline ll query(int l,int r){
    l = l+P-1;r = r+P+1;
    //先下放标记 
    for(int i=DEP;i;--i) push_down(l>>i,1<<i),push_down(r>>i,1<<i); 
    ll res = 0;
    while(l^1^r){
        if(~l&1) res+=tr[l^1]; 
        if(r&1) res+=tr[r^1]; 
        //由于标记已下放，所以无需再累加标记的贡献 
        l>>=1; r>>=1;
    }
    return res;
  }

六、优化效果

1、时间复杂度

开始的时候也提到了：递归线段树常数大的瓶颈在于其需要对树进行递归遍历以找到目标节点，然后回溯进行信息维护。
zkw 线段树仅仅只是优化了递归寻找目标节点这样的遍历过程的常数。

如果是追求常数或者注重优化遍历，那 zkw 线段树的优化就比较明显了；如果要维护较为复杂的信息，那么显然这点常数并不是很够看，此时就需要在其他地方上做改进了。

2、空间复杂度

zkw 线段树需要开三倍空间，普通线段树如果不使用动态开点需要开四倍空间。

相较于普通线段树，zkw 线段树代码好理解也比较简洁，不会出现忘建树和忘终止递归的问题，而且满二叉树结构的确定性让手造数据也比较方便。
对于一些维护信息复杂的题目，zkw 线段树的优势在于手推时思路更加清晰。

如果性格比较内向，不敢用递归线段树进行递归维护信息。
想用 zkw 递推实现更多更强的操作怎么办！

zkw 线段树实现其他线段树结构

一、引入

1、关于 zkw 线段树

本人认为：狭义的 zkw 线段树是指建立出满二叉树结构、节点间的父子关系严格规定、一切信息从叶子节点开始向上维护、通过循环递推实现维护过程。
另外：张昆玮大佬的 PPT 中提到，为了减小递归带来的常数，出现了汇编版的非递归线段树。
所以本人的理解是：广义的 zkw 线段树指通过循环递推而非递归实现的线段树。

2、关于优化效果

基于多数线段树结构的特点，导致大部分时候必须上下循环两次维护信息，所以此时 zkw 线段树更多优化的是代码的简洁程度和理解难度（当然了，对常数也有一些优化）。

二、可持久化线段树

1、介绍

可持久化线段树与普通线段树的区别在于，其支持修改和访问任意版本。
举个例子：给定一个序列 a_N，对它进行一百万次操作，然后突然问你第十次操作后的序列信息。

朴素的想法是对于每次操作都建一棵线段树，空间复杂度是 O(3mn) 的。
可以发现：
修改后，大部分节点并没有受到影响，所以考虑只对受影响的节点新建对应节点。其余没受影响的节点直接与原树共用节点，就等同于新建了一棵修改后的线段树。

2、单点修改单点查询

每次单点修改后，只有叶子节点到根节点的那一条链上的点会受到影响。
所以我们只需要对受影响的这条链新建一条对应的链，其余没受影响的节点直接和待修改版本共用即可。

对于本次要修改的位置，在以原始序列 a_N 建立的初始线段树中，其对应的叶子节点到根的链上的节点分别为 tl，当前新节点为 now，下一个新节点为 new：
如果 tl 为左儿子，那么 now 的左儿子为 new，右儿子为 tl 对应在待修改树上节点的兄弟节点；
如果 tl 为右儿子，那么 now 的右儿子为 new，左儿子为 tl 对应在待修改树上节点的兄弟节点。

其实就是新建节点的位置与初始树上的节点位置分别对应。
看图（节点内数字为节点编号）：在原序列上修改一个位置:

在第一次修改后的序列上，再修改一次：

继续在第一次修改后的序列上做修改：

我们发现新建的链在新树上的位置，与初始树上的链在初始树上的位置，是相同的。
所以我们新建节点时，新节点的位置跟随对应的初始树上的节点的位置进行移动。

由于版本间需要以根节点做区分（因为使用叶子节点会非常麻烦），所以修改和查询操作只能从根节点开始自上而下进行，防止不同版本的存储出现问题。
所以我们需要多一个记录：当前节点的左右儿子。

对于 tl 到根的链如何快速求得，我们前面讲“哨兵”的时候已经讲过实现，接下来就是模拟整个新建节点过程即可。
同时，新建节点的节点编号依次递增，操作后进行自下而上维护信息也很方便：

//建初始线段树
  while(P<=n+1) P<<=1,++DEP; NOW = (1<<(DEP+1))-1;//最后一个节点的编号
  for(int i=1;i<=n;++i) read(tr[P+i]); rt[0] = 1;//初始树根为1
  for(int i=P-1;i;--i) son[i][0]=i<<1,son[i][1]=i<<1|1;//记录子节点 0为左儿子；1为右儿子
//...
//...
  inline void update(int i,int vi,int val,int l){
    int tl = l+P;//在初始树上对应的叶子节点编号
    int v = rt[vi];//待修改线段树的根
    rt[i] = l = ++NOW;//新线段树的根
    for(int dep=DEP-1; dep>=0 ;--dep,l = NOW){
        //模拟节点更新过程
        if((tl>>dep)&1) son[l][0] = son[v][0],son[l][1] = ++NOW,v = son[v][1];
        else son[l][0] = ++NOW,son[l][1] = son[v][1],v = son[v][0];
    }
    tr[l] = val;//更新最后的叶子节点

    //自下而上维护信息（如果有需要的话）
    //for(int dep=1;dep<=DEP;++dep) tr[l-dep]=tr[son[l-dep][0]]+tr[son[l-dep][1]];
  }

版本查询与修改相同，从根开始模拟子树选取：

//
  inline int query(int vi,int l){
    int tl = l+P;//在初始树上对应的叶子节点编号
    l = rt[vi];//当前版本的根
    for(int dep=DEP-1; dep>=0 ;--dep) l=son[l][(tl>>dep)&1];
    return tr[l];//返回叶子节点值
  }

3、区间修改区间查询

目前我了解到的信息是：只能做区间加。
可持久化线段树中有大量的公用节点，所以标记不能下放且修改要能够用永久化标记维护，否则会对其他版本产生影响。

那么考虑如何做区间加。

1. 标记永久化：省去标记下放以减小常数同时防止对其他版本产生影响；
2. 预处理时记录子树大小，查讯时累加标记值。

不同的是：

1. 需要对区间新建节点；
2. 修改时对照初始树上节点的轨迹进行移动；
3. 修改需要自上而下进行，然后再自下而上做一遍维护（类似递归回溯）。

三、权值线段树

1、介绍

普通线段树维护的是信息，权值线段树维护的是信息的个数。
权值线段树相当于在普通线段树上开了一个桶，用于处理信息个数，以单点修改和区间查询实现动态全局第 k 大。

2、查询全局排名

在权值线段树中，节点存信息出现的次数：

//
  inline void update(int l,int k){
    l += P; tr[l] += k;//k为信息出现次数 
    for(l>>=1; l ;l>>=1) tr[l] = tr[l<<1]+tr[l<<1|1];
  }

当前数字的相对大小位置向前的前缀和，即为当前数字在全局中的排名：

//
  inline int get_rank(int r){//查询第r个数的全局排名 
    int l = 1+P-1;//做区间[1,r]的前缀和 
    r += P+1;
    int res = 0;
    while(l^1^r){
        if(~l&1) res+=tr[l^1];
        if(r&1) res+=tr[r^1];
        l>>=1; r>>=1; 
    }
    return res;
  }

3、动态全局第 k 大

基于线段树的结构，第 k 大的二分实现其实就在线段树上查找左右子树的过程。
查询第 k 大时，借助线段树的结构，以左右子树选取来模拟二分过程即可：

//
  inline int K_th(int k){
    int l = 1,dep = 0;
    while(dep<DEP){
        if(tr[l<<1]>=k) l=l<<1;//模拟二分 
        else k-=tr[l<<1],l=l<<1|1;
        ++dep;
    }
    return l-P;//减去虚点编号，得到原数组中的编号 
  }

4、前驱与后继

有时还需要查询 k 的前驱和后继。