一、简介
zkw 线段树专门用于线段树卡常，同时码量比普通线段树要小。
原理是通过将线段树补成完全二叉树，直接找到第 \(i\) 个叶子节点（编号为 \(p+i\) ），然后从下往上更新，从而避免递归。
这里常数 p=1<<(__lg(n)+1) ，编号为 \(p\) 和 \(p+n+1\) 的叶子为虚点，编号为 \(p+1\sim p+n\) 的叶子允许访问，编号大于 \(p+n+1\) 的节点不会被访问到，所以只需要开三倍空间。
二、操作
时间复杂度同普通线段树，后面不再单独分析。
初始化
一口气把信息读到叶子上，然后从下往上更新即可。
void build()
{
for(int i=1;i<=p;i++) sum[p+i]=a[i];
for(int i=(p+n)>>1;i>=1;i--) sum[i]=sum[i<<1]+sum[i<<1|1];
}
注意从 (p+n)>>1 开始更新是为了防止越界。
单点修改，区间查询
先解决单点修改的问题。如果信息有可加性，一路修改即可。
void modify(int x,int v)
{
for(x+=p;x>=1;x>>=1) sum[p]+=v;
}
如果信息没有可加性，单点修改然后一路 pushup 。
void modify(int x,int v)
{
x+=p,sum[p]+=v;
for(;x!=1;x>>=1) pushup(x>>1);
}
再解决区间查询的问题。线段树和 \(\texttt{01trie}\) 本质上是一回事，我们的目标是把区间 \([l,r]\) 拆成 \(\texttt{01trie}\) 上的 \(\mathcal O(\log n)\) 棵子树。
首先将 \([l,r]\) 转化为 \((l-1,r+1)\) ，然后让左右端点同步往上跳。
如果左端点是其父节点的左儿子，那么右子树一定完全包含在区间中。
如果右端点是其父节点的右儿子，那么左子树一定完全包含在区间中。
跳到左右端点互为兄弟节点时，循环结束。
ll query(int l,int r)
{
ll res=0;
for(l=p+l-1,r=p+r+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) res+=sum[l^1];
if(r&1) res+=sum[r^1];
}
return res;
}
区间修改，单点查询
同普通线段树，我们需要引入懒标记。
由于只涉及到单点查询，我们不需要处理信息与信息的合并，甚至可以只用一个数组同时存储标记（非叶节点）和信息（叶节点）！
void modify(int l,int r,int v)
{
for(l=p+l-1,r=p+r+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) sum[l^1]+=v;
if(r&1) sum[r^1]+=v;
}
}
ll query(int x)
{
ll res=0;
for(x+=p;x;x>>=1) res+=sum[x];
return res;
}
区间修改，区间查询
这需要我们对懒标记有足够深刻的理解：
线段树要求：标记与标记可合并，标记与信息可合并，信息与信息可合并。
标记与信息的关系：
- 节点 \(p\) 的标记打给 \(p\) 的整棵子树（不包含 \(p\) 自身），标记对 \(p\) 的影响已经体现在 \(val_p\) 中，叶节点的标记无意义。
- 节点 \(p\) 的信息 \(val_p\) 表示考虑 \(p\) 子树内（包含 \(p\) 自身）的所有标记时，第 \([l_p,r_p]\) 个叶子的信息之和。
标记永久化
普通线段树查询方法：收集 \(1\to fa_p\) 的标记，若节点 \(p\) 对应的区间 \([l_p,r_p]\) 完全包含于查询区间 \([l,r]\) ，计算节点 \(p\) 的贡献。
标记永久化一般要求标记和信息都满足交换律。
我们需要对 \((l-1,r+1)\) 拆出来的 \(\mathcal O(\log n)\) 个区间更新信息并打上标记，同时左右端点的信息也要更新，因为它与 \([l,r]\) 有交叉。
拆区间的过程中我们跳到左右端点为兄弟节点时就停下了，接下来还要一路更新到根。
以区间加为例，维护左右端点对应的区间与修改区间 \([l,r]\) 的交集长度 \(lcnt,rcnt\) 即可。
void modify(int l,int r,int v)
{
ll lcnt=0,rcnt=0,cnt=1;
for(l=p+l-1,r=p+r+1;l^r^1;l>>=1,r>>=1,cnt<<=1)
{
sum[l]+=v*lcnt,sum[r]+=v*rcnt;
if(~l&1) add[l^1]+=v,sum[l^1]+=v*cnt,lcnt+=cnt;
if(r&1) add[r^1]+=v,sum[r^1]+=v*cnt,rcnt+=cnt;
}
for(;l;l>>=1,r>>=1) sum[l]+=v*lcnt,sum[r]+=v*rcnt;
}
那如果是区间覆盖这种不满足交换律的标记呢？
维护标记的时间戳也能做，让时间戳较大的标记覆盖较小标记，代码懒得写了。
区间查询的步骤和区间修改大致相同，别忘了最后要跳到根。
ll query(int l,int r)
{
ll lcnt=0,rcnt=0,cnt=1,res=0;
for(l=p+l-1,r=p+r+1;l^r^1;l>>=1,r>>=1,cnt<<=1)
{
res+=add[l]*lcnt+add[r]*rcnt;
if(~l&1) res+=sum[l^1],lcnt+=cnt;
if(r&1) res+=sum[r^1],rcnt+=cnt;
}
for(;l;l>>=1,r>>=1) res+=add[l]*lcnt+add[r]*rcnt;
return res;
}
个人感觉标记永久化的用途没有标记下传广，而且理解起来难度较大，建议能用标记下传就用标记下传。
标记下传
普通线段树查询方法：
- 如果 \([l_p,r_p]\subseteq[l,r]\) ，统计节点 \(p\) 的信息。
- 如果 \([l_p,r_p]\cap[l,r]=\varnothing\) ，直接返回。
- 下传标记后分别统计左右二字的信息。
注：从上述过程也可看出叶节点的标记无意义。
以区间加区间求和为例，为方便下传标记，我们需要记录每个节点代表区间的左右端点，在初始化时自底向上更新即可。
注意虚点 \(p+n+1\) 的祖先节点由于右端点没有定义，所以维护的信息是错误的。但是它们维护的标记是正确的，拆区间也不会用到它们的信息。
struct node
{
int l,r;
ll add,sum;
}f[3*maxn];
void build()
{
for(int i=0;i<=n+1;i++) f[p+i]={i,i,0,a[i]};
for(int i=(p+n)>>1;i>=1;i--) f[i]={f[ls].l,f[rs].r,0,f[ls].sum+f[rs].sum};
}
如果维护的是区间加区间最值等操作，那么没有必要维护左右端点，代码可以更加简洁。
记录线段树深度 \(dep\) ，对 \(p+l-1\) 和 \(p+r+1\) 的祖先节点从上往下 pushdown ，然后正常拆区间即可。
注意拆区间时需要同步 pushup ，并且最后要 pushup 到根节点。
void modify(int l,int r,ll v)
{
static int dep=__lg(p);
l=p+l-1,r=p+r+1;
for(int i=dep;i>=1;i--) pushdown(l>>i),pushdown(r>>i);
for(;l^r^1;l>>=1,r>>=1)
{
if(~l&1) pushadd(l^1,v);
if(r&1) pushadd(r^1,v);
pushup(l>>1),pushup(r>>1);
}
for(;l!=1;l>>=1) pushup(l>>1);
}
区间查询除了先 pushdown 以外没啥其他变化。
ll query(int l,int r)
{
static int dep=__lg(p);
l=p+l-1,r=p+r+1;
for(int i=dep;i>=1;i--) pushdown(l>>i),pushdown(r>>i);
ll res=0;
for(;l^r^1;l>>=1,r>>=1)
{
if(~l&1) res+=f[l^1].sum;
if(r&1) res+=f[r^1].sum;
}
return res;
}
三、效率对比
zkw 线段树主要卡的是在树上遍历的时间，如果瓶颈在维护信息（如矩阵）那么收效甚微。
\(\texttt{LOJ130}\) ：单点修改，区间查询， \(n=q=10^6\) 。
- 树状数组：代码， \(\texttt{511B,270ms}\) 。
- zkw 线段树：代码， \(\texttt{768B,256ms}\) 。
- 普通线段树：代码， \(\texttt{1010B,515ms}\) 。
\(\texttt{LOJ131}\) ：区间修改，单点查询， \(n=q=10^6\) 。
- 树状数组：代码， \(\texttt{554B,287ms}\) 。
- zkw 线段树：代码， \(\texttt{642B,281ms}\) 。
- 普通线段树：代码， \(\texttt{1232B,708ms}\) 。
\(\texttt{LOJ132}\) ：区间修改，区间查询， \(n=q=10^6\) 。
- 树状数组：代码， \(\texttt{760B,426ms}\) 。
- 标记永久化 zkw 线段树：代码， \(\texttt{1203B,392ms}\) 。
- 标记下传 zkw 线段树：代码， \(\texttt{1452B,600ms}\) 。
- 普通线段树：代码， \(\texttt{1251B,855ms}\) 。