一种轻量级平衡树

command_block · 2023-02-07 22:00:58 · 个人记录

【注：现在（2月7日）还在考佛一模，复杂度证明是摸鱼写的，不知道对不对，还请诸位帮忙验证一下。如果得到多人确证，就可以宣布新平衡树的诞生了 OvO】

【又注：新树还没有命名，我打算叫它“自适应无旋 Leafy Tree”（或者俗称“广义线段树 EXSGT”，因为整个思路真的很线段树），不知道这个名字是不是已经被用过了】

【又又注：可能有人知道这玩意是我初二的时候想出来的……没错！证明鸽了整整四年】

feature：

• 能以均摊 \Theta(\log n) 复杂度完成一系列区间问题（能力和 Splay 类似）

• 易于初学者学习掌握，容易在赛场上写出来，不易遗忘

  • 无旋转，逻辑简单，易于调试

  • 是 Leafy Tree ，维护信息时和线段树类似

• 常数较之 Splay 显著更小

• 不需要重量平衡策略 / 随机平衡策略

weak point：

• 需要双倍节点数，增大空间消耗（Leafy Tree 的共同点）

• 需要频繁新建和销毁节点

• 不能简易地可持久化

总的来说，在赛场上解决区间问题时，几乎总是 Splay 的上位替代。弱点不怎么影响使用。

【目前先简单写写，把基本原理和证明交代清楚，等我有空了再写一个更适合初学者的版本，或者谁会了也可以自己写】

算法介绍

以 P3391 【模板】文艺平衡树 为例来介绍。

我们维护的是一个广义线段树，如图：

当要对某个区间进行操作时，将被该区间部分包含的节点删去。余下的森林要么被区间完全包含，要么完全不包含。

若要对 Middle 部分进行翻转，先把各棵树的顺序翻转，然后把每棵树都打上翻转标记（同块状链表）。

最后，将所有树排成一排，在其上建立类似线段树的结构。

（放大查看）

#include<algorithm>
#include<cstdio>
#define MaxN 100500
using namespace std;
struct Node{
  int l,r,c;bool rv;
  inline void rev(){rv^=1;swap(l,r);}
}a[MaxN<<1];
int top,rub[MaxN];
inline int cre(){
  int u=rub[top--];
  a[u].l=a[u].r=a[u].c=a[u].rv=0;
  return u;
}
int wfc,wfl,wfr,tn,rt;
int tl,tr,tm,bl[MaxN],bm[MaxN],br[MaxN];
inline void up(int u)
{a[u].c=a[a[u].l].c+a[a[u].r].c;}
inline void ladd(int u){
  if (a[u].rv){
    a[u].rv=0;
    a[a[u].l].rev();
    a[a[u].r].rev();
  }
}
void spilt(int l,int r,int u)
{
  if (r<wfl)bl[++tl]=u;
  else if (wfl<=l&&r<=wfr)bm[++tm]=u;
  else if (wfr<l)br[++tr]=u;
  else {
    ladd(u);
    int mid=l+a[a[u].l].c-1;
    spilt(l,mid,a[u].l);
    spilt(mid+1,r,a[u].r);
    rub[++top]=u;
  }
}
int _merge(int x,int y){
  int u=cre();
  a[u].l=x;a[u].r=y;
  up(u);return u;
}
int st[MaxN];
void merge()
{
  int w=0;
  for (int i=1;i<=tl;i++)st[++w]=bl[i];
  for (int i=1;i<=tm;i++)st[++w]=bm[i];
  for (int i=1;i<=tr;i++)st[++w]=br[i];
  while(w>1){
    for (int i=2;i<=w;i+=2)
      st[i>>1]=_merge(st[i-1],st[i]);
    if (w&1)st[(w+1)>>1]=st[w];
    w=(w+1)>>1;
  }rt=st[1];
}
void dfs(int u){
  ladd(u);
  if (a[u].c==1){printf("%d ",u);return ;}
  dfs(a[u].l);dfs(a[u].r);
}
void build(int l,int r,int &u)
{
  if (l==r){a[u=l].c=1;return ;}
  u=++tn;
  int mid=(l+r)>>1;
  build(l,mid,a[u].l);
  build(mid+1,r,a[u].r);
  up(u);
}
int n,m;
int main()
{
  scanf("%d%d",&n,&m);
  tn=n;build(1,n,rt);
  for (int i=1;i<=m;i++){
    scanf("%d%d",&wfl,&wfr);
    tl=tr=tm=0;spilt(1,n,rt);
    for (int i=1;i<=tm;i++)a[bm[i]].rev();
    reverse(bm+1,bm+tm+1);
    merge();
  }dfs(rt);
  return 0;
}

以下是 P7739 [NOI2021] 密码箱 考场代码，以供参考。

#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 200500
using namespace std;
const int xtq=998244353;
struct Mat{int a[2][2];};
const Mat I=(Mat){{{1,0},{0,1}}};
Mat operator * (const Mat &B,const Mat &A){
  Mat C;
  C.a[0][0]=(1ll*A.a[0][0]*B.a[0][0]+1ll*A.a[0][1]*B.a[1][0])%xtq;
  C.a[0][1]=(1ll*A.a[0][0]*B.a[0][1]+1ll*A.a[0][1]*B.a[1][1])%xtq;
  C.a[1][0]=(1ll*A.a[1][0]*B.a[0][0]+1ll*A.a[1][1]*B.a[1][0])%xtq;
  C.a[1][1]=(1ll*A.a[1][0]*B.a[0][1]+1ll*A.a[1][1]*B.a[1][1])%xtq;
  return C;
}
inline Mat xmat(int x)
{return (Mat){{{x,1},{1,0}}};}
inline Mat calc(int e,int w)
{return xmat(1+e)*xmat(1+w);}
struct Data{int c1,c2,x1,x2;Mat s;};
void mul(const Data &L,const Data &R,int Lc,int Rc,Data &S)
{
  if (L.c1==Lc){S=R;S.c1+=L.c1;return ;}
  if (L.c1+L.c2==Lc){
    S.c1=L.c1;
    if (R.c1){
      S.c2=L.c2-1;
      if (R.c1+R.c2<Rc)
        S.s=calc(R.c1-1,R.c2)*R.s;
      else S.s=I;
    }else {
      S.c2=L.c2+R.c2;
      S.s=R.s;
    }
    if (R.c1+R.c2==Rc){
      if (R.c1){S.x1=R.c1;S.x2=R.c2+1;}
      else S.x1=S.x2=0;
    }else {S.x1=R.x1;S.x2=R.x2;}
    return ;
  }
  S.c1=L.c1;S.c2=L.c2;
  if (R.c1+R.c2<Rc){S.x1=R.x1;S.x2=R.x2;}
  else {
    if (R.c1&&L.x2>1){S.x1=R.c1;S.x2=R.c2+1;}
    else {S.x1=L.x1+R.c1;S.x2=L.x2+R.c2;}
  }
  if (R.c1+R.c2<Rc){
    if (R.c1&&L.x2>1)S.s=L.s*xmat(L.x1)*xmat(L.x2-1)*calc(R.c1-1,R.c2)*R.s;
    else S.s=L.s*xmat(L.x1+R.c1)*xmat(L.x2+R.c2)*R.s;
  }else {
    if (R.c1&&L.x2>1)S.s=L.s*xmat(L.x1)*xmat(L.x2-1);
    else S.s=L.s;
  }
}
Data xdat(bool op){
  Data S;
  S.x1=S.x2=-1;S.s=I;
  if (op){S.c1=1;S.c2=0;}
  else {S.c1=0;S.c2=1;}
  return S;
}
struct Node{
  bool fl,rev;int l,r,c;Data ls[2],rs[2];
  inline void ladd(bool _fl,bool _rev){
    if (_fl){fl^=1;swap(ls[0],ls[1]);swap(rs[0],rs[1]);}
    if (_rev){rev^=1;swap(l,r);swap(ls[0],rs[0]);swap(ls[1],rs[1]);}
  }
}a[MaxN<<1];
void Init(bool x,Node &A){
  A.c=1;
  A.ls[0]=A.rs[0]=xdat(x);
  A.ls[1]=A.rs[1]=xdat(x^1);
}
int tn,rub[MaxN],tob;
int cre()
{return tob ? rub[tob--] : ++tn;}
inline void up(int u){
  int l=a[u].l,r=a[u].r;
  a[u].c=a[l].c+a[r].c;
  mul(a[l].ls[0],a[r].ls[0],a[l].c,a[r].c,a[u].ls[0]);
  mul(a[l].ls[1],a[r].ls[1],a[l].c,a[r].c,a[u].ls[1]);
  mul(a[r].rs[0],a[l].rs[0],a[r].c,a[l].c,a[u].rs[0]);
  mul(a[r].rs[1],a[l].rs[1],a[r].c,a[l].c,a[u].rs[1]);
}
inline void ladd(int u){
  if (a[u].fl||a[u].rev){
    a[a[u].l].ladd(a[u].fl,a[u].rev);
    a[a[u].r].ladd(a[u].fl,a[u].rev);
    a[u].fl=a[u].rev=0;
  }
}
int wfl,wfr,sl[MaxN],tl,sr[MaxN],tr,sm[MaxN],tm;
void spilt(int l,int r,int u)
{
  if (r<wfl){sl[++tl]=u;return ;}
  if (wfr<l){sr[++tr]=u;return ;}
  if (wfl<=l&&r<=wfr){sm[++tm]=u;return ;}
  int mid=l+a[a[u].l].c-1;
  ladd(rub[++tob]=u);
  spilt(l,mid,a[u].l);spilt(mid+1,r,a[u].r);
}
int merge(int l,int r){
  int u=cre();
  a[u].l=l;a[u].r=r;
  up(u);return u;
}
int rt,st[MaxN];
void build()
{
  int tn=0;
  for (int i=1;i<=tl;i++)st[++tn]=sl[i];
  for (int i=1;i<=tm;i++)st[++tn]=sm[i];
  for (int i=1;i<=tr;i++)st[++tn]=sr[i];
  while(tn>1){
    for (int i=2;i<=tn;i+=2)
      st[i/2]=merge(st[i-1],st[i]);
    if (tn&1)st[(tn+1)/2]=st[tn];
    tn=(tn+1)/2;
  }tl=tm=tr=0;rt=st[1];
}
void print(Data A,int u){
  Mat ans=xmat(A.c1)*xmat(A.c2+1)*A.s;
  if (A.x1!=-1)ans=ans*xmat(A.x1);
  if (A.x2!=-1)ans=ans*xmat(A.x2);
  printf("%d %d\n",ans.a[0][0],ans.a[0][1]);
}
int n,m;char s[MaxN];
int main()
{
  scanf("%d%d%s",&n,&m,s+1);
  for (int i=1;i<=n;i++)
    Init(s[i]=='E',a[sm[i]=cre()]);
  tm=n;build();
  print(a[rt].ls[0],rt);
  char op[10],ch;
  for (int qt=1;qt<=m;qt++){
    scanf("%s",op);
    if (op[0]=='A'){
      scanf("%s",op);
      sl[tl=1]=rt;
      Init(op[0]=='E',a[sr[tr=1]=cre()]);
      n++;
    }
    if (op[0]=='F'){
      scanf("%d%d",&wfl,&wfr);
      spilt(1,n,rt);
      for (int i=1;i<=tm;i++)
        a[sm[i]].ladd(1,0);
    }
    if (op[0]=='R'){
      scanf("%d%d",&wfl,&wfr);
      spilt(1,n,rt);
      reverse(sm+1,sm+tm+1);
      for (int i=1;i<=tm;i++)
        a[sm[i]].ladd(0,1);
    }
    build();print(a[rt].ls[0],rt);
  }return 0;
}

复杂度证明

设节点 u 子树的“高度”为 u 到最远叶节点之间的节点数。记为 h_u。

设子树 T 的势能为 \Phi(T)=\sum_{u\in T}\log_2h_u 。

可以把模型简化成这样：每次将树分裂成 [1,p],[p+1,n] 两部分，然后合回去。

显然除了被删除和重建的节点，其他节点的 h 都没有变化。

我们要估计被删除节点 \log h 和的下界 S_0，重建节点 \log h 和的上界 S_1。

设从浅到深第 k 棵子树（注意，不是图中标号，图中标号是从左到右）的高度是 H_k ，从浅到深 第 k 个被删除节点的 h 为 h_k 。则 h_k 为 H_k 不断加一的后缀 \max ，把 +1 忽略掉，将 h_k 放缩为 H_k 的后缀 \max。

将 H_k 的限制放缩为每个分别 \leq n 。

操作后在线段树上取子树 \max 在适当地 +1 就能得到新的 h 。可以不考虑 +1 ，而在 \log h 总和中加上 \Theta(m\log\log m) 。

考虑 H 的排布怎样最差（S_1-S_0 最大），显然 H 是单调递减的，否则可以增大其中某一项使 S_0 不变而 S_1 增大。

取出最优方案 H 的最后一段非 1 的连续段，这一段比全是 1 好，若把这一段增大一些但不越过上一段，也一定更好，矛盾。于是 H 肯定是浅的部分一段相同取上界 n，深的部分全是 1 。

• 设浅的部分有 $k$ 个 $n$，$k$ 接近 $m$ 的情况是平凡的。考虑末尾的 $\Theta(m)$ 个 $1$ （考虑不断 $+1$ 的影响），这部分势能和为 $\Theta(m\log m)$ 。对于之前的 $k$ 个 $n$ ，势能和为 $k\log n$ 。
• $k$ 个 $n$ 在左右关系上是连续的，在线段树中紧密排列为一个区间，则影响到的点为 $k+\Theta(\log m)$ 个。这部分势能和为 $k\log n+\Theta(\log m\log n)$ 。 其余部分 $\Theta(m\log\log m)$。

势能变化量为 \Theta(\log m\log n)-\Theta(m\log m) ，接下来容易证明均摊复杂度 O(\log n)。