ZKW线段树

Yao_ · 2023-11-13 20:29:15 · 个人记录

ZKW线段树

背景介绍

由张昆玮在“统计的力量”中提出。

算法介绍

特点

非递归式线段树，特点是操作自下而上，通过循环完成操作。节点的对应关系严格规定。

优点

==速度远快于普通线段树，略次于树状数组==。空间复杂度在 n*2 左右。而且完整保留了原数组。

缺点

区间修改难以pushdown，使用标记永久化，==无法维护标记有顺序要求的情况==。

示例

区间加减的标记就是没有顺序要求的典型，在第 i 次操作时，前 i-1 次操作的顺序不影响此次查询的结果。同理还有区间乘。但加和乘同时出现时就不适用了。 我们以区间和为例，实现单点修改查询和区间修改查询。

• 我们需要将第 i 个节点读入到 tr[p+i] 中，多数博客的 p 需要这样算 for(p=1;p<n+2;p<<=1);，但直接令 p=n ，也通过了，下面代码均 p==n 。
• 标记永久化的标记，个人习惯将包含在修改范围内的区间直接添加标记，将与修改范围有交集的区间修改tr[]，即保证每个节点的值实际上是 tr[x]+\sum_{i=x}^{root} add[i]
• 建树，我们直接读入到叶子节点

  int tr[N*2],add[N*2];
  cin>>n;
  for(int i=n+1;i<=n*2;i++)cin>>tr[i];//建树，直接读到叶子节点
  for(int i=n;i>=1;i--)tr[i]=tr[i<<1]+tr[i<<1|1];//只在建树时有一次pushup操作

  单点操作

• 单点修改

  //给第x个数加k
  for(x+=n;x;x>>=1)tr[x]+=k;

• 单点查询

  int query(int x)
  {
      int res=tr[x+=n];
      for(;x;x>>=1)res+=add[x];
      return res;
  }

  区间操作 区间操作中，我们需要将闭区间 [l,r] 扩展成开区间 (l,r)，维护两个指针，p=l-1,q=r+1。（这里的 l 和 r 对应 tr[n+l] 和 tr[n+r] ）当 p 为左节点时右节点为根的子树是所求区间的子集，当 q 为右节点时左节点为根的子树是所求区间的子集。一直追溯到 l 和 r 互为兄弟节点，这些子集的并等于所求区间。 同时，我们记录左右节点分别贡献的长度，用来计算懒标记。

• 区间修改

  void update(int x,int y,int k)//给[x,y]每个数加k
  {
      x+=n-1,y+=n+1;
      int sl=0,sr=0,si=1;//si为以当前层任一节点为根的子树的节点数
      while(x^1^y)//即l+1!=r，即l/2!=r/2,即 l 和 r 不为兄弟节点。
      {
          tr[x]+=sl*k,tr[y]+=sr*k;//维护有交集的区间的tr
          if(!(x&1))add[x+1]+=k,sl+=si;//维护子集区间的add
          if(y&1)add[y-1]+=k,sr+=si;
          x>>=1,r>>=1,si<<=1;
      }
      for(;x;x>>=1,y>>=1)tr[x]+=sl*k,tr[y]+=sr*k;//更上层的区间都是有交集的，维护tr
      //注意，上一行代码，初次进入循环时x和y是兄弟节点，所以分开处理，随后的循环实际上x==y
  }

  整个过程中，我们可以把和操作有关的区间分为两种：有交集的，作为修改区间的子集的。有交集的这样处理：从当前层来看，左侧在修改区间内的所有点是一些以左指针为根的树的子树，与修改区间的交集的节点数就是 sl ，所以每次循环都需要 tr[x]+=sl*k ，相应的也处理右节点。作为修改区间子集的则直接 +k 。最后，更上层的区间，是包含修改区间的，它们也属于有交集的区间，也要处理 tr[] 值。

• 区间查询

  int query(int x,int y)
  {
      x+=n-1,y+=n+1;
      int sl=0,sr=0,si=1;
      int sum=0;
      while(x^1^y)
      {
          if(!(x&1))sum+=tr[x+1]+add[x+1]*si,sl+=si;//该子树所有点需要加该点携带的标记
          if(y&1)sum+=tr[y-1]+add[y-1]*si,sr+=si;
          x>>=1,y>>=1,si<<=1;
      }
      for(;x;x>>=1,y>>=1)sum+=add[x]*sl+add[y]*sr;
      return sum;
  }

  可以看到，区间查询和区间修改的框架是一致的。在循环中，我们边寻找查询区间的所有子树，边计算子树的值。以左为例，找到一个子树时，先把 tr[x＋1] 值加上，以该点为根的子树所有节点都需要加上 add[x+1] 这个没向下传的标记值。