数据结构颓废计划V-ZKW线段树

参见:“统计的力量-线段树全接触” 清华大学 张昆玮 参见:[总结][数据结构]ZKW线段树详解 区间修改相关，暂时还没读懂。 这是一种奇怪的卡常技巧

Description

时间复杂度:

查询: O(log2N)

修改: O(log2N)

空间复杂度:

O(2∗N)

定义

树状数组与线段树的混血儿，非递归版本，位运算加速，常数奇小。

树的构造

void init() { for(int i=M-1;i>=1;i--) T[i]=T[i<<1]+T[(i<<1)+1]; }

对于一个形式非 [0,2N) 的树，我们在原序列后面强行补零，使其成为这样一个形式。此时 M 即为此时序列的补零后的长度。但是考虑到开闭区间的各种坑爹问题，一般只使用[1,2N−2]这一部分。输入时，我们将序列输入到 [M+1,M+len] 区间内。然后用init()函数构树。

树的单点修改与区间求和

void update( int n , int v ){ for(T[n+=M]=v,n>>=1;n;n>>=1) T[n]=T[n<<1]+T[(n<<1)+1]; }

很简明的自底至顶修改方式。由于非递归且位运算，速度很快，常数小。

int query( int s , int t ) { int Ans=0; for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1) if(-s&1)Ans+=T[s^1]; if(t&1)Ans+=T[t^1]; } return Ans; }

与普通线段树同理。

进阶：区间修改

TODO