从ZKW线段树看线段树的性质

最近遇到了很多线段树性质相关的题目，故在此做一个总结。

常规建树

代码

void build(int l,int r,int rt){
    do_something();
	if(l==r){
		return ;
	}
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}

性质

左儿子长度不小于右儿子。
节点编号 rt 描述了从根到自身的父子关系，也间接描述了该点长度和根节点长度的关系，具体的，根节点的最大或最小长度是一个关于该节点长度的一次函数，这个一次函数只由 rt 决定。
编号最大的节点不一定是 r，事实上可以在 $\log n$ 的时间内求出，如果左儿子多一层，那么一定在左儿子，否则在右儿子，决定某个儿子是否会多一层，当且仅当目前长度为奇数，且 popcount 值为 2。

例题

一道简单的题

一道比较简单的题

非常规建树

非常规建树一般会指定建树的 mid 位置。

区间覆盖数

即覆盖一个区间 $[l,r]$ 的最小线段数。

先转成 $(l,r)$，然后依次跳叶节点 $l,r$ 的父亲，先判断 $l,r$ 的父亲是否相同，相同就可以走人了。

如果 $l$ 作为左儿子跳上去，那么该节点的右儿子会对该区间贡献一次，因为该节点的右儿子的父亲超出了区间，但自身在区间内。如果 $r$ 作为右儿子跳上去，那么该节点的左儿子会对区间贡献一次，原因同理，如此就可以找到区间覆盖数，这也是 ZKW线段树的原理。

例题

给定一个指定 mid 节点的线段树，需要支持 rotate 一个节点，rotate 定义为伸展树(splay)的 rotate，强制在线询问区间覆盖数。

先考虑没有修改，那么就是找到 $l,r$ 的 $lca$，然后一路统计 $l$，$r$ 作为左右儿子的次数即可，可以用倍增快速解决。

修改本质上就是断边和加边，用 LCT 维护。

ZKW线段树简介

建树

为了方便，需要建一棵有 $2^k$ 个节点的树，主要是为了让高度相同，求出第一个不小于 $n$ 的 $2$ 的次幂的方式：k=32-__builtin_clz(n-1)。

建树时注意没有数据的地方应该弄成 “0”，且注意初始数组大小，并且要开 $2^k+5$ 以免溢出。

建树时记录单点的编号。

单点修改

直接从下往上改就可以了。

1
2
3

void update(int rt,int c){
    a[rt].mx1=c;while(rt!=1)push_up(rt>>=1);
}

区间查询

个人习惯闭区间，且有效区间落在 $[1,n]$。

查询时看是否为兄弟节点，如果是就停下，否则对于左端点，是左子树则加上兄弟右子树。对于右端点，是右子树则加上兄弟左子树。另外需要加上两个端点。

node query(int lrt,int rrt){
    if(lrt==rrt)return a[lrt];
    node ret=a[lrt]+a[rrt];
    while(lrt>>1!=rrt>>1){
        if(~lrt&1)ret=ret+a[lrt+1];
        if(rrt&1)ret=ret+a[rrt-1];
        lrt>>=1,rrt>>=1;
    }
    return ret;
}

注意特判区间长度为 $1$ 的情况。

区间修改

由于是从下往上查询，所以只能采用标记永久化的方式，像查询那样做修改，在对应的点上打 Tag。

效率

对于 $10^5,3\times 10^5,10^6$ 的随机数据进行了测试，效率改进因子约为 $0.4$。