[数据结构与算法]模板：全局平衡二叉树

所谓全局平衡二叉树，就是在全局来看都很平衡的二叉树。

（逃

前言

这个引言倒是实话（雾
可以把一些本来只能用树剖两个 log 做的问题在单log 时间复杂度解决。
修改通常来说只能支持单点修改。
查询解决链上问题或者全局问题更为方便（但子树似乎也是可以的）
常数比较大，但总比LCT强。

解析

树剖其实可以看成对每一条重链上的节点都维护一棵线段树，同一条重链上的节点享受同样的查询复杂度。
但是我们发现这样“看似平衡”的数据结构其实并不平衡，因为有的节点可能有非常多的轻儿子，而有的节点可能根本没有轻儿子，前者在大部分数据中都会更多的被访问到。
因此引出了全局平衡二叉树的思想。

定义一个节点的权值 $va{l}_x$ 为其所有轻儿子子树大小+1。
全局平衡二叉树的结构和LCT十分相似。先对原树进行重链剖分，然后对每个重链维护一棵二叉查找树，这里每次选择的区间断点不是中点（那样就是线段树了），而是按照 $val$ 找到的带权重心，并把二叉查找树根节点的父亲设为原树重链头的父亲。
（于LCT不同的是，这里二叉查找树的结构是静态的。）
本人的写法中二叉搜索树的非叶节点都是虚点。

对于一个单点修改，修改其信息后不断跳父亲更新即可。

对于一个链上查询，对应的是若干条重链的前缀和一条重链的区间，前者由建树的定义不难发现每次消耗复杂度必然siz翻倍，故是 $\log n$ 的，后者由于树高为 log，故也是 $\log n$ 的。

子树就在子树根节点的二叉查找树上找一找需要的节点信息合并即可。

代码

P4751 【模板】“动态DP”&动态树分治（加强版）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

const int N=2e6+100;
const int inf=1e9+100;
const bool Flag=0;

int n,m;
int tot;

struct matrix{
  int x,y;
  int a[3][3];
  matrix(int X=0,int Y=0,int u=-inf,int v=-inf,int p=-inf,int q=-inf):x(X),y(Y){
    a[1][1]=u;a[1][2]=v;a[2][1]=p;a[2][2]=q;
  }
};
matrix operator * (const matrix &u,const matrix &v){
  matrix res(u.x,v.y);
  for(int k=1;k<=u.y;k++){
    for(int i=1;i<=u.x;i++){
      int tmp=u.a[i][k];
      for(int j=1;j<=v.y;j++) res.a[i][j]=max(res.a[i][j],tmp+v.a[k][j]);
    }
  }
  return res;
}

vector<int>e[N];
int a[N],fa[N],siz[N],val[N],hson[N];
int s0[N],s1[N];
void dfs1(int x,int f){
  siz[x]=1;fa[x]=f;
  for(int to:e[x]){
    if(to==f) continue;
    dfs1(to,x);
    siz[x]+=siz[to];
    if(siz[to]>siz[hson[x]]) hson[x]=to;
  }
  val[x]=siz[x]-siz[hson[x]];
  return;
}
struct node{
  matrix ans;
  int fa,ls,rs;
}tr[N];
int nod[N];
inline void pushup(int x){
  tr[x].ans=tr[tr[x].rs].ans*tr[tr[x].ls].ans;
}
int build(int l,int r,int f){
  if(l==r){
    int x=nod[l];
    matrix o(2,2,s0[x],s1[x],s0[x],-inf);
    tr[x].ans=o;
    tr[x].fa=f;
    return x;
  }
  int cur(0),sum(0),now(0);
  for(int i=l;i<=r;i++) sum+=val[nod[i]];    
  for(int i=l;i<=r;i++){
    cur+=val[nod[i]];
    if(cur*2<sum) continue;
    if(i==r) --i;
    now=++tot;
    tr[now].fa=f;
    tr[now].ls=build(l,i,now);
    tr[now].rs=build(i+1,r,now);
    break;
  }
  pushup(now);
  return now;
}
inline void ins(int rt,int op){
  int f=tr[rt].fa;
  if(f){
    s0[f]+=op*max(tr[rt].ans.a[1][1],max(tr[rt].ans.a[1][2],max(tr[rt].ans.a[2][1],tr[rt].ans.a[2][2])));
    s1[f]+=op*max(tr[rt].ans.a[1][1],tr[rt].ans.a[2][1]);
    matrix o(2,2,s0[f],s1[f],s0[f],-inf);
    tr[f].ans=o;
  }
}
int dfs2(int x,int f){
  int top(0);
  for(int p=x;p;p=hson[p]){
    for(int to:e[p]){
      if(to==hson[p]||to==fa[p]) continue;
      dfs2(to,p);
    }
  }
  for(int p=x;p;p=hson[p]){
    nod[++top]=p;
  }
  int rt=build(1,top,f);
  if(f) ins(rt,1);
  return rt;
}
inline void upd(int x,int y){
  if(!x) return;
  s1[x]=y;
  for(int p=x;p;p=tr[p].fa){
    if(tr[p].fa&&tr[tr[p].fa].ls!=p&&tr[tr[p].fa].rs!=p) ins(p,-1);
    if(p==x) tr[p].ans.a[1][2]=y;          
    if(p>n) pushup(p);
    if(tr[p].fa&&tr[tr[p].fa].ls!=p&&tr[tr[p].fa].rs!=p) ins(p,1),p=tr[p].fa;
  }
  return;
}

signed main(){
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();m=read();
  for(int i=1;i<=n;i++) s1[i]=a[i]=read();
  for(int i=1;i<n;i++){
    int x=read(),y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  tot=n;
  dfs1(1,0);
  int rt=dfs2(1,0),lst(0);
  for(int i=1;i<=m;i++){
    int x=read()^lst,y=read();
    upd(x,s1[x]+y-a[x]);
    a[x]=y;
    printf("%d\n",lst=max(tr[rt].ans.a[1][1],max(tr[rt].ans.a[1][2],max(tr[rt].ans.a[2][1],tr[rt].ans.a[2][2]))));
  }
  return 0;
}

practice

SP2666 QTREE4 - Query on a tree IV
本题的难点是如果对每个点开一个堆存储所有轻儿子到父亲的合法点距离最大值，修改时需要对堆操作，复杂度就两个log了。
一个神奇且小清新的优化方法是把整棵树三度化，这样就只有一个轻儿子，不必开堆了。

代码实现参考了 @hehezhou 的博客。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

const int N=4e5+100;
const int inf=1e9;
const bool Flag=0;

int n,m;

#define pr pair<int,int>
#define mkp make_pair
vector<pr>e[N];
int dep[N],tot;
int lson[N],wson[N],siz[N],val[N];
inline void link(int x,int y){
  //debug("link: %d %d\n",x,y);
  if(!lson[x]) lson[x]=y;
  else wson[x]=y;
}
void dfs0(int x,int f){
  link(x+n,x);
  for(int i=0;i<(int)e[x].size();i++){
    if(e[x][i].first==f){
      e[x].erase(e[x].begin()+i);
      break;
    }
  }
  for(int i=0;i<(int)e[x].size();i++){
    dep[e[x][i].first+n]=dep[x];
    dep[e[x][i].first]=dep[x]+e[x][i].second;
    dfs0(e[x][i].first,x);
  }
  for(int i=1;i<(int)e[x].size();i++) link(e[x][i-1].first+n,e[x][i].first+n);
  if(!e[x].empty()) link(x,e[x][0].first+n);
}
struct node{
  int l,r,ls,rs,lmax,rmax,ans,pre,suf,fa;
}tr[N];
void dfs1(int x){
  siz[x]=1;
  if(wson[x]){
    dfs1(wson[x]);
    siz[x]+=siz[wson[x]];
  }
  if(lson[x]){
    dfs1(lson[x]);
    siz[x]+=siz[lson[x]];
  }
  if(siz[wson[x]]<siz[lson[x]]) swap(lson[x],wson[x]);
  val[x]=siz[x]-siz[wson[x]];
  return;
}
int zhan[N];
int build(int l,int r,int f){
  if(l==r){
    tr[zhan[l]].pre=tr[zhan[l]].suf=zhan[l];
    tr[zhan[l]].l=tr[zhan[l]].r=l;
    tr[zhan[l]].fa=f;
    return zhan[l];
  }
  int sum(0),cur(0),now(0);
  for(int i=l;i<=r;i++) sum+=val[zhan[i]];
  for(int i=l;i<=r;i++){
    cur+=val[zhan[i]];
    if(cur*2<sum) continue;
    if(i==r) --i;
    now=++tot;
    tr[now].ls=build(l,i,now);
    tr[now].rs=build(i+1,r,now);
    break;
  }
  tr[now].l=l;tr[now].r=r;
  tr[now].pre=zhan[l];tr[now].suf=zhan[r];
  tr[now].fa=f;
  if(Flag) printf("now=%d (%d %d)\n",now,l,r);
  return now;
}
int dfs2(int x,int f){
  int top=0;
  for(int p=x;p;p=wson[p]) zhan[++top]=p;
  if(Flag) for(int i=1;i<=top;i++) printf("%d ",zhan[i]);
  if(Flag) puts("\n");
  int rt=build(1,top,f);
  for(int p=x;p;p=wson[p]){
    if(lson[p]) tr[p].ls=dfs2(lson[p],p);
  }
  return rt;
}
bool ban[N];
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
inline void pushup(int x){
  if(tr[x].l==tr[x].r){
    int d=tr[ls(x)].lmax+dep[tr[ls(x)].pre]-dep[x];
    if(!ban[x]){
      tr[x].lmax=tr[x].rmax=max(d,0);
      tr[x].ans=max(tr[ls(x)].ans,0);
    }
    else{
      tr[x].lmax=tr[x].rmax=d;
      tr[x].ans=tr[ls(x)].ans;
    }
    return;
  }
  else{
    tr[x].lmax=max(tr[ls(x)].lmax,tr[rs(x)].lmax+(dep[tr[rs(x)].pre]-dep[tr[ls(x)].pre]));
    tr[x].rmax=max(tr[rs(x)].rmax,tr[ls(x)].rmax+(dep[tr[rs(x)].suf]-dep[tr[ls(x)].suf]));
    tr[x].ans=max(max(tr[ls(x)].ans,tr[rs(x)].ans),tr[ls(x)].rmax+tr[rs(x)].lmax+dep[tr[rs(x)].pre]-dep[tr[ls(x)].suf]);
    return;
  }  
}
void init(int x){
  if(!x) return;
  if(tr[x].l==tr[x].r){
    init(tr[x].ls);
  }
  else{
    init(tr[x].ls);
    init(tr[x].rs);
  }
  pushup(x);
  if(Flag) printf("x=%d lmax=%d rmax=%d ans=%d\n",x,tr[x].lmax,tr[x].rmax,tr[x].ans);
  return;
}

signed main(){
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  tr[0].lmax=tr[0].rmax=tr[0].ans=-inf;
  n=read();
  for(int i=1;i<n;i++){
    int x=read(),y=read(),w=read();
    e[x].push_back(mkp(y,w));
    e[y].push_back(mkp(x,w));
  }
  tot=n+n;
  dfs0(1,0);
  dfs1(1);
  int rt=dfs2(1,0);
  for(int i=n+1;i<=tot;i++) ban[i]=1;
  init(rt);
  if(Flag) for(int i=1;i<=tot;i++) printf("i=%d dep=%d\n",i,dep[i]);
  m=read();
  char c;
  for(int i=1;i<=m;i++){
    scanf(" %c",&c);
    if(c=='A'){
      if(tr[rt].ans<0) puts("They have disappeared.");
      else printf("%d\n",tr[rt].ans);
    }
    else{
      int x=read();
      ban[x]^=1;
      for(;x;x=tr[x].fa) pushup(x);
    }
    if(Flag) init(rt);
    if(Flag) puts("");
  }
  return 0;
}
/*
5
1 2 -8
2 3 -5
1 4 -7
4 5 -6
 */