浅谈ZKW线段树之lazy标记
zkw线段树的网上讲解似乎很多，我就不介绍大纲了。
zkw线段树的核心思想就是尽量省去递归来减小常数
比如在build操作
普通线段树：
void build(int p,int l,int r)
{
if (l==r){tree[p]=a[l];return;}
int mid=(l+r)>>1,ls=p<<1,rs=ls|1;
build(ls,l,mid),build(rs,mid+1,r);
updata(i);
}
zkw线段树：
void build()
{
for (m=1;m常数又小又简短
然而我想说的重点不在这里,如果你想学zkw线段树请右转zkw的论文《统计的力量》,
下面我将介绍如何在zkw线段树中使用\(lazy\)标记。
我们都知道如何在线段树上打标记。(没学过lazy标记就不要点进来)
我们只需要在对应区间打标记，这和普通线段树没什么区别。
但维护标记就比较麻烦了，这里有一种非常简单的维护方法
一般的zkw操作都是这样的
void change(int l,int r)
{
for (l=l+m-1,r=r+m+1;l^r^1;l>>=1,r>>=1,updata(l),updata(r))
{
if (~l&1) ...
if (r&1) ...
}
l>>=1;
while (l) updata(l),l>>=1;
}
而我想说的更新方法非常简单，只需要在for()中加一个\(push\)函数
void change(int l,int r)
{
for (l=l+m-1,r=r+m+1,push(l),push(r);l^r^1;l>>=1,r>>=1,updata(l),updata(r))
{
if (~l&1) ...
if (r&1) ...
}
l>>=1;
while (l) updata(l),l>>=1;
}
\(push\)函数长这样：
void push(int x)
{
int top=0;
while (x) sta[++top]=x,x>>=1;
while (top>1) pushdown(sta[top--]);
}
上面的\(pushdown\)就是普通线段树的\(pushdown\)；
代码的意思就是用栈模拟普通线段树的\(lazy\)下传；
是不是很好用，zkw线段树也能打标记，普通线段树可以退役了。