【数据结构】zkw线段树

因为本人在写一道水题:滑动窗口(Luogu p1886),时发现普通线段树常数太大,浑身解数试完了都不能把常数优化下去,无奈只可去学新的线段树——zkw线段树。

出处:清华大学 张昆玮 -ppt 《统计的力量》

这其实是非递归的线段树。

为了不处理特殊情况,假设二叉树总是满的,如果不是,假设你的区间是$[0,1000)$,就设为$[0,1024)$即可。

然后应用堆式储存方式:

$N$的左儿子是 $N << 1$

$N$的右儿子是$N << 1\ |\ 1$

$N$的父亲是$N >> 1$

换成二进制就是:

这好像就是一个$Trie$树,存放的是$100,101,110,111$四个串,每个节点存的是以这个节点为前缀的所有节点和.例如$1$中存的是所有四个以$1$开头的和。

似乎从 $100$ 到$ 111$ 就正好是原数组,于是……下标减 $4$ 就行了?

我们可以直接找到一个数对应的叶子,而且不用自顶向下慢慢地找啊找,“直接加$ 4$ ”多简单!

我们设底层节点数$M=2^{depth}$,那么$M$可以这样得到:

for(M = 1;M < (n + 2);M <<= 1);

查询操作:

Func Query(s,t)  // 询问从s到t闭区间
    s = s – 1, t = t + 1;  // 变为开区间
    s += M, t += M;  // 找到叶子位置
    While not ((s xor t) == 1) do
        If ((s and 1) == 0) Answer += Tree[s + 1];
        If ((t and 1) == 1) Answer += Tree[t – 1];
        s = s >> 1, t = t >> 1;

真实码:

for (s = s + M - 1,t = t + M + 1;s ^ t ^ 1;s >>= 1,t >>= 1) {
    if (~s & 1) Ans += T[s ^ 1];//l % 2 == 0
    if (t & 1) Ans += T[t ^ 1];//r % 2 == 1
}

操作修改:

Func Change(n,NewValue)
    n += M;
    Tree[n] = NewValue;
    While n > 1 do
        n = n >> 1;
        Tree[n]  = Tree[2n] + Tree[2n+1];

真实码:

for(T[n += M] = V,n >>= 1;n;n >>= 1)
    T[n]=T[n + n] + T[n + n + 1];

仅使用了两倍原数组的空间

其中还完整地包括了原数组

构造容易:

For i=M-1 downto 1 do T[i]=T[2i]+T[2i+1];
inline void build(){
    for(M = 1;M < (n + 1);m <<= 1);
    for(int i = M + 1;i <= M + n;i++){
        t[i].min = t[i].max = read();
    }
    for(int i = M - 1;i;i--){
        maintain(p);
    }
}

从$M+1$处开始输入原因:(来自知乎@Mike He
是为了询问,假设我们查询的区间就是$[1,N]$,这时为了进行查询我们会将$[1,N]$转化为$(0,N-1)$,看上去没有区别,其实是有区别的。由于位于$0$上的数字是否能被统计上与左端点位置相关,$(L=M+1-1=M )$,如果从$M$开始输入会导致查询时统计不到位于$0$上的信息,因为$L$初始位置就是第一个叶子的位置了$(L=M)$但是如果换成 $M+1$ 开始,查询时$L$的位置依旧是$L=M+1-1=M$,但是第一个叶子的位置在$M+1$ 上,这样就能够统计到那个叶子上的信息啦。因此要从$M+1$开始输入信息。

太好写了

自底向上,只访问一次,而且不一定访问到顶层

实践中非常快,与树状数组接近

区间修改要用差分思想,留坑待填。