全局平衡二叉树学习笔记
jrxxx
·
·
算法·理论
\large\color{red}\text{Global Biased Tree}
据说这玩意写动态 \text{DP} 吊打树剖，不仅好写而且快。
于是抽了一点时间来学习一下。
一篇讲得很好的博客
另一篇讲得很好的博客
（有图！）
算法理解
就我个人看来，“全局平衡二叉树”其实相当于是 \text{LCT} 的静态版（别较真，我不知道哪个先有）——它将 \text{LCT} 的实链剖分和 \text{splay} 换成了重链剖分和\bold{bst}，因此失去了改变树形的能力，但拥有了更小的常数。
与 \text{LCT} 类似的，“全局平衡二叉树”具有如下性质：
1.由很多棵二叉树通过轻边连起来组成，每一棵二叉树维护了原树的一条重链，其中序遍历的顺序就是这条重链深度单调递增的顺序。每个节点出现且仅出现在一棵二叉树中。
2.边分为重边和轻边，重边是包含在二叉树中的边。轻边从一颗二叉树的根节点指向它所对应的重链顶端节点的父节点。轻边“认父不认子”。
而这里，普通 $\text{bst}$ 并不能带来优秀的复杂度，我们要在这些棵~~不普通的~~ $\text{bst}$ 上下一些心思，使之具有一些性质（最精妙的地方）。
具体地，对一条重链，以**轻子树 $size$ 和 $+1$** 作为点权，每次求出**加权重心**作为根，再向以该点分开的左右两半递归建左右子树。最后将整条重链的树根连向该重链顶点的父亲。
这样虽然单个重链的二叉树不一定平衡，但是所有二叉树和轻边组成的树满足树高为 $O(\log n)$。因为每向上跳一条边（无论轻边还是重边），子树 $size$ 至少增加一倍。
## 应用
“全局平衡二叉树”不算热门算法，很多时候也都可以用树剖代替。
但是在单点修改或链修改一些简单信息时都表现得十分优异，可以说是吊打树剖。
## 实例
### [【模板】动态 DP](https://www.luogu.com.cn/problem/P4719)
树，点带权，支持单点修改点权，求树上最大独立集。
朴素转移：
$$
\begin{aligned}
f[u][0]&=\sum \max(f[v][1],f[v][0])\\
f[u][1]&=w_u+\sum f[v][0]
\end{aligned}
$$
另外定义 $p$ 为重儿子， $g[u][0/1]$ 为除去重儿子贡献的答案。
则：
$$
\begin{aligned}
g[u][0]&=\sum_{v!=p} \max(f[v][1],f[v][0])\\
g[u][1]&=w_u+\sum_{v!=p} f[v][0]\\
f[u][0]&=g[u][0]+ \max(f[p][1],f[p][0])\\
f[u][1]&=g[u][1]+ f[p][0]\\
\end{aligned}
$$
定义“加法”为取 $\max$，“乘法”为数的加法，可以证明（但我不会）这样的矩阵乘法满足结合律。
于是有：
$$
\begin{bmatrix}g_{u,0}&g_{u,0}\\g_{u,1}&-\infty\end{bmatrix}
\times
\begin{bmatrix}f_{p,0}\\f_{p,1}\end{bmatrix}
=\begin{bmatrix}f_{u,0}\\f_{u,1}\end{bmatrix}
$$
发现改一个点的点权会影响其到根的整条链上答案，但在原树上暴力跳最劣一次 $O(n)$。
如果树剖，利用跳到根只会经过 $O(\log n)$ 条轻边这一性质，用线段树维护重链，实现只在跳轻边时算答案，复杂度 $O(\log^2 n)$。
但是，在全局平衡二叉树上，直接暴力跳到根经过的点数就是 $O(\log n)$ 的！不需要做其他处理了，只用跳时分类讨论一下轻重边就行。
代码：
```cpp
#include<bits/stdc++.h>
using std::max;
inline int rd(int x=0,int y=1,char c=getchar())
{
for(;!isdigit(c);c=getchar())if(c=='-')y=-1;
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*y;
}
const int inf=0x3f3f3f3f;
struct mat
{
int a[2][2];
mat(){memset(a,0,sizeof a);}
int* operator[](int x){return a[x];}
const int* operator[](int x)const{return a[x];}
const mat operator*(const mat &b)const
{
mat res;
res[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
res[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
res[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
res[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
return res;
}
int mx(){return max(a[0][0],a[1][0]);}
void I(){a[0][1]=a[1][0]=-inf,a[0][0]=a[1][1]=0;}
};
const int N=1e5+7;
int n,w[N];
std::vector<int> G[N];
int son[N],siz[N],dfn[N],id[N],tot;
void dfs1(int u,int fr)
{
siz[u]=1;
for(int v:G[u])
if(v!=fr)
{
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u)
{
dfn[u]=++tot;
id[tot]=u;
if(!son[u])return;
dfs2(son[u]);
for(int v:G[u])
if(!dfn[v])dfs2(v);
}
namespace GBT
{
struct node
{
int ls,rs,fa;
mat g,f;//f只在重链链顶是真正的f
}tr[N];
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define fa(p) tr[p].fa
#define g(p) tr[p].g
#define f(p) tr[p].f
inline void init()
{
g(0).I();f(0).I();
for(int i=1;i<=n;++i)
g(i)[1][0]=w[i],g(i)[1][1]=-inf;
}
inline void up(int p)
{
f(p)=f(ls(p))*g(p)*f(rs(p));
}
inline void dvt(int p,int w)//重链链顶给它父亲贡献（w=-1表示撤销贡献）
{
int x=fa(p);
g(x)[0][0]+=w*f(p).mx();
g(x)[0][1]=g(x)[0][0];
g(x)[1][1]+=w*f(p)[0][0];
}
int cbld(int l,int r)//对一条重链建二叉树
{
int sz=0,tot=0,x,i;
for(i=l;i<=r;++i)
tot+=siz[id[i]]-siz[son[id[i]]];
for(i=l;(sz<<1)<tot;++i)
sz+=siz[id[i]]-siz[son[id[i]]];
x=id[--i];
if(i>l) ls(x)=cbld(l,i-1),fa(ls(x))=x;
if(i<r) rs(x)=cbld(i+1,r),fa(rs(x))=x;
up(x);
return x;
}
int bld(int u,int fr)//建树
{
int x=u,y=fr,z;
for(;x;x=son[y=x])
for(int v:G[x])
if(v!=son[x]&&v!=y)
fa(z=bld(v,x))=x,dvt(z,1);
return cbld(dfn[u],dfn[y]);
}
void upd(int u,int x)//单点改
{
g(u)[1][0]+=x-w[u];
w[u]=x;
for(;u;u=fa(u))
if(u!=ls(fa(u))&&u!=rs(fa(u)))
dvt(u,-1),up(u),dvt(u,1);
else up(u);
}
}
int main()
{
int m,i,x,y,RT;
n=rd(),m=rd();
for(i=1;i<=n;++i)
w[i]=rd();
for(i=1;i<n;++i)
{
x=rd(),y=rd();
G[x].push_back(y);
G[y].push_back(x);
}
dfs1(1,0);
dfs2(1);
GBT::init();
RT=GBT::bld(1,0);
while(m--)
{
x=rd(),y=rd();
GBT::upd(x,y);
printf("%d\n",GBT::tr[RT].f.mx());
}
return 0;
}
```