【学习笔记】树论—点分树（动态点分治）

# **【学习笔记】树论—点分树（动态点分治）** [$\mathcal{My}\ \mathcal{Blog}$](https://www.cnblogs.com/Xing-Ling/p/12976848.html) ## **【前言】** ~~氡态淀粉质 / 垫粪鼠~~ 点分治是一种树上分治算法，常用以处理树上路径相关信息的统计。在点分治的基础上加以变化，构造一颗支持快速修改的重构树，就成了点分树。 虽说名字里带个动态，但也有人认为它应该算作静态数据结构。 （据教练所说，点分树是近几年的新兴热门考点...于是就有了这篇总结...） ## **一：【算法理解及复杂度分析】** 前置芝士：需要有良好的 [**点分治**](https://www.luogu.com.cn/problem/P3806) 基础。 点分治的核心思想在于依据重心划分子连通块，其良好的性质保证了最多只会分治 $\log n$ 层。有了这一特性，便可使用各种暴力计算答案。 那么我们**按照分治递归的顺序提一颗新树出来**，易知树高是 $O(\log n)$ 的。 具体地说，**对于每一个找到的重心，将上一层分治时的重心设为它的父亲**，得到一颗大小不变、最多 $\log n$ 层的虚树（或者理解为重构树。亦可称点分树，意义一样）。 在这颗虚树上，奇妙的性质产生了：**虚树上所有点的子树大小之和为** $O(n\log n)$ 。 证明很简单：每个点会被从根到它的路径上最多 $\log n$ 个祖先所统计，因此总复杂度为 $\sum_{i=1}^{n}depth(i)=O(n\log n)$ 。 如果要对某个点进行修改操作，直接在虚树上暴力跳父亲，改变 $O(\log n)$ 个祖先的虚子树信息即可。 > Q: 虚子树的信息与原树有啥关系呢？ A: **点 $x$ 在虚树上的子树集合就是原树中以 $x$ 为重心（分治中心）时所囊括到的连通块。** 如下图（黑边为原树，灰边为虚树，蓝色编号为分治的顺序）：   以 $1$ 为重心做分治时，所囊括的连通块为 $\{1,2,3,4,5,6,7,8,9,10\}$，删去该点后被划分为了 $\{2,3,4,5,6\},\{7,8,9,10,11\}$ 两个子连通块； 以 $2$ 为重心做分治时，所囊括的连通块为 $\{2,3,4,5,6\}$，删去该点后被划分为了 $\{3,4\},\{5\},\{6\}$ 三个子连通块； 以 $7$ 为重心做分治时，所囊括的连通块为 $\{7,8,9,10,11\}$，删去该点后被划分为了 $\{8,9\},\{10,11\}$ 两个子连通块； ...... 那么能用它求什么呢？ 比如我们要统计某个点 $x$ 到其他所有点的距离之和，即 $\sum_{y=1}^{n}dis(x,y)$ 。对于任意一个 $y$，首先在虚树上找到它与 $x$ 的 $lca$（或者说囊括连通块同时包含 $x,y$ 的所有虚树节点中深度最深的那一个），易知在以此点为重心划分子连通块时 $x,y$ 会首次被分割开来，因此该点必定在原树的 $x,y$ 路径上。 所以我们只需要在这些 $lca$ 的虚子树中寻找 $y$ 即可，此时记录虚子树信息的作用便显现出来了。 而对于一个 $x$，可能的 $lca$ 最多存在 $\log n$ 个，因此通常使用暴力枚举+简单容斥的方法来统计 $y$ 的贡献。具体见下文 **【 计算贡献】**。 ## **二：【算法实现】** **[【模板】点分树 / 震波 $\text{[P6329]}$](https://www.luogu.com.cn/problem/P6329) [$\text{[Bzoj3730]}$](http://www.lydsy.com/JudgeOnline/problem.php?id=3730)** **【题目大意】** 维护一颗带点权树，需要支持两种操作：修改 $x$ 的点权，查询与点 $x$ 距离不超过 $K$ 的点权值之和。 ### **1.【建点分树】** 找到第一个重心 $rt$ 后，先遍历整颗树得到 $rt$ 的子树信息，然后删去 $rt$，得到若干个连通块（$rt$ 的不同子树）。分别找到这些子树里的重心（在虚树上使其成为 $rt$ 的儿子），然后递归处理这些子连通块。 实际上大体和淀粉质是相同的，只是将淀粉质中“计算答案”的操作改为了“统计虚子树信息”。 ### **2.【计算贡献】** 以下用 $fa_i$ 表示点 $i$ 在虚树上的父亲，$subtree(i)$ 为点 $i$ 在虚树上的子树集合，$fatree(i)$ 为点 $i$ 在虚树上的祖先集合，$dis(i,j)$ 为 $i,j$ 两点在原树上的距离，$A_i$ 为点 $i$ 的点权。 设： $f_1(i,j)=\sum_{x\in subtree(i),dis(x,i)\leqslant j}A_x$，即虚树上 $i$ 的子树中与 $i$ 距离小于等于 $j$ 的点权值之和； 为了除去某一个虚儿子子树的贡献，还需要： $f_2(i,j)=\sum_{x\in subtree(i),dis(x,fa_i)\leqslant j}A_x$，即虚树上 $i$ 的子树中与 $fa_i$ 距离小于等于 $j$ 的点权值之和。 在一次查询 $(x,k)$ 中，对于虚树上的一对父子节点 $(i,fa_i)$，$subtree(fa_i)-subtree(i)$ 对答案的贡献为 $G(i,fa_i)=f_1(fa_i,k-dis(x,fa_i))$ $-$ $f_2(i,k-dis(x,fa_i))$ 。 则有 $ans(x,k)=f_1(x,k)+$ $\sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)$，注意前面那个 $f_1(x,k)$ 是因为容斥求和后 $subtree(x)$ 没有被统计进去，所以要单独拿出来算。 修改点权时同理，把所有对于 $f_1,f_2$ 的查询操作换成修改就可以了。 ### **3.【维护信息】** 计算 $dis$ 可以用树剖求 $\text{LCA}$ 在线查询。 也可以用欧拉序 + $\text{ST}$ 表。或者用在每次找完根后，$dfs$ 遍历一下子树预处理 $dis$ 数组。两者都是花费 $O(n\log n)$ 的时间省下了 $O(q\log^2 n)$ 的时间，但经实际测试，$\text{ST}$ 表被树剖吊起来锤，预处理与树剖不相上下，emm...过于柯怕 维护 $f_1,f_2$ 可以对每个节点开一棵动态开点线段树，下标为 $dis$（即 $f_1,f_2$ 的第二维）。时间复杂度为 $O(n\log^2 n)$，空间按照 $dis$ 范围的上界压缩一下可以做到 $O(n\log n)$（如果偷懒统一使用同一个上界 $[0,n]$ 可能会达到 $O(n\log^2 n)$）。但线段树常数略大，可能会被卡（~~虽然我过了~~），换成树状数组会稳一点。 >Q: 树状数组咋动态开点啊？ A: 当然是用动态分配内存的 $vector$ 啊！ ### **4.【实现细节】** - 子连通块大小不要直接用 $\text{size(to)}$（这都是从淀粉质那里遗留下来的问题了，但依旧有人不重视） - 一般不需要把虚树的实际形态建出来，但如果能用到的话，注意不要和原树搞混。 - 树状数组大小要设置得当。设 $now=|subtree(i)|$，由于 $i$ 在 $subtree(i)$ 中为重心，所以 $f_1(i,j)$ 中 $j$ 的值域为 $[0\sim \frac{now}{2}]$，$f_2(i,j)$ 中 $j$ 的值域为 $[1\sim now]$ 。由于下标可以为 $0$，在树状数组内部还需要统一向后移一位。也就是说 $f_1,f_2$ 的大小要分别设置为 $\frac{now}{2}+1$ 和 $now+1$ 。 - 如果预处理了每个点在虚树上的祖先，修改 / 查询 中跳父亲时需要倒序枚举（具体见代码）。 - 关于卡常：点分树做题经常会用到 $\text{vector},$ $\text{set},$ $\text{multiset},$ $\text{priority queue}$ 之类的东西，如果您嫌弃它们太慢且不愿开 $\text{O2}$，自备几个能代替 $\text{STL}$ 的模板吧.... ### **5.【Code】** （线段树的代码就不放了） **【在线查询 Dis】** ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define LL long long #define Re register int using namespace std; const int N=1e5+3,inf=2e9,logN=17; int n,m,o,x,y,T,op,lastans,A[N],deep[N],head[N]; struct QAQ{int to,next;}a[N<<1]; inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct LCA{ int fa[N],top[N],son[N],size[N]; inline void dfs1(Re x,Re Fa){ size[x]=1,deep[x]=deep[fa[x]=Fa]+1; for(Re i=head[x],to;i;i=a[i].next) if((to=a[i].to)!=Fa){ dfs1(to,x),size[x]+=size[to]; if(size[son[x]]<size[to])son[x]=to; } } inline void dfs2(Re x,Re rt){ top[x]=rt; if(!son[x])return; dfs2(son[x],rt); for(Re i=head[x],to;i;i=a[i].next) if((to=a[i].to)!=fa[x]&&to!=son[x])dfs2(to,to); } inline void build(){dfs1(1,0),dfs2(1,1);} inline int lca(Re x,Re y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]])swap(x,y); x=fa[top[x]]; } if(deep[x]>deep[y])swap(x,y); return x; } }T1; inline int Dis(Re x,Re y){return deep[x]+deep[y]-(deep[T1.lca(x,y)]<<1);}//查询原树中点x,y的距离 struct BIT{ int n;vector<int>C; inline void build(Re N){C.resize((n=N)+1);}//使用到的上限为n,空间开n+1 inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}//由于dis可能为0,所以在BIT里面统计向后移一位，查询同理 inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}//注意要和维护的上界取最小值，防止越界 }TR1[N],TR2[N]; int rt,sum,fa[N],vis[N],maxp[N],size[N]; inline void getrt(Re x,Re fa){//获取该连通块的重心 size[x]=1,maxp[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa) getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]); maxp[x]=max(maxp[x],sum-size[x]); if(maxp[x]<maxp[rt])rt=x; } inline void sakura(Re x,Re Fa){//处理重心x所囊括的连通块 Re now=sum;vis[x]=1,fa[x]=Fa; TR1[x].build(now/2+1),TR2[x].build(now+1);//由重心性质可知,TR1会使用[0,now/2],TR2会使用[1,now]，向后移一位变为[1,now/2+1]和[2,now+1] for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt,x);//注意子连通块大小不要直接用size[to] } inline void change(Re x,Re v){ TR1[x].add(0,v);//subtree(x) for(Re i=x;fa[i];i=fa[i]){//在虚树上面跳父亲 Re tmp=Dis(x,fa[i]); TR1[fa[i]].add(tmp,v); TR2[i].add(tmp,v); } } inline int ask(Re x,Re K){ Re ans=TR1[x].ask(K);//subtree(x) for(Re i=x;fa[i];i=fa[i]){//在虚树上面跳父亲 Re tmp=Dis(x,fa[i]);if(tmp>K)continue; ans+=TR1[fa[i]].ask(K-tmp); ans-=TR2[i].ask(K-tmp); } return ans; } int main(){ // freopen("123.txt","r",stdin); in(n),in(T),m=n-1; for(Re i=1;i<=n;++i)in(A[i]); while(m--)in(x),in(y),add(x,y),add(y,x); T1.build(),sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt,0); for(Re i=1;i<=n;++i)change(i,A[i]); while(T--){ in(op),in(x),in(y),x^=lastans,y^=lastans; if(op)change(x,y-A[x]),A[x]=y; else printf("%d\n",lastans=ask(x,y)); } } ``` **【预处理 Dis】** ```cpp #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #define LL long long #define Re register int using namespace std; const int N=1e5+3,inf=2e9,logN=17; int n,m,o,x,y,T,op,lastans,A[N],head[N]; struct QAQ{int to,next;}a[N<<1]; inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct BIT{ int n;vector<int>C; inline void build(Re N){C.resize((n=N)+1);}//使用到的上限为n,空间开n+1 inline void add(Re x,Re v){++x;while(x<=n)C[x]+=v,x+=x&-x;}//由于dis可能为0,所以在BIT里面统计向后移一位，查询同理 inline int ask(Re x){++x,x=min(x,n);Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}//注意要和维护的上界取最小值，防止越界 }TR1[N],TR2[N]; int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][20],fdis[N][20]; inline void getrt(Re x,Re fa){//获取该连通块的重心 size[x]=1,maxp[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa) getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]); maxp[x]=max(maxp[x],sum-size[x]); if(maxp[x]<maxp[rt])rt=x; } inline void getdis(Re x,Re rt,Re fa,Re d){//遍历该连通块预处理dis frt[x][++gs[x]]=rt,fdis[x][gs[x]]=d;//顺手把祖先也存下来，后面一起访问 for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d+1); } inline void sakura(Re x){//处理重心x所囊括的连通块 Re now=sum;vis[x]=1,getdis(x,x,0,0); TR1[x].build(now/2+1),TR2[x].build(now+1);//由重心性质可知,TR1会使用[0,now/2],TR2会使用[1,now]，向后移一位变为[1,now/2+1]和[2,now+1] for(Re i=head[x],to;i;i=a[i].next) if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt);//注意子连通块大小不要直接用size[to] } inline void change(Re x,Re v){ TR1[x].add(0,v);//subtree(x) for(Re i=gs[x];i>=2;--i){//注意要倒序枚举 Re tmp=fdis[x][i-1]; TR1[frt[x][i-1]].add(tmp,v); TR2[frt[x][i]].add(tmp,v); } } inline int ask(Re x,Re K){ Re ans=TR1[x].ask(K);//subtree(x) for(Re i=gs[x];i>=2;--i){//注意要倒序枚举 Re tmp=fdis[x][i-1];if(tmp>K)continue; ans+=TR1[frt[x][i-1]].ask(K-tmp); ans-=TR2[frt[x][i]].ask(K-tmp); } return ans; } int main(){ // freopen("123.txt","r",stdin); in(n),in(T),m=n-1; for(Re i=1;i<=n;++i)in(A[i]); while(m--)in(x),in(y),add(x,y),add(y,x); sum=n,maxp[rt=0]=inf,getrt(1,0),sakura(rt); for(Re i=1;i<=n;++i)change(i,A[i]); while(T--){ in(op),in(x),in(y),x^=lastans,y^=lastans; if(op)change(x,y-A[x]),A[x]=y; else printf("%d\n",lastans=ask(x,y)); } } ``` ## **三：【常见套路、经典例题】** （**注：** 后面的题都不再用文字具体阐述 $f_1,f_2$ 含义，且只放核心代码） ### **1.【另外两道板题】** - [**烁烁的游戏** $\text{[Bzoj4372]}$](http://lydsy.com/JudgeOnline/problem.php?id=4372) （和模板题震波类似，用一个数据结构进行维护） - [$\text{Atm}$ **的树** $\text{[Bzoj4317] [Bzoj2051] [Bzoj2117]}$](http://www.lydsy.com/JudgeOnline/problem.php?id=4317)（二分答案后又是一只震波） ### **2.【开店】** **[开店 $\text{[HNOI2015] [P3241]}$](https://www.luogu.com.cn/problem/P3241)** **【题目大意】** 维护一颗带点权、边权树，每次给出 $x,l,r$，查询 $\sum_{l\leqslant A_y \leqslant r}dis(x,y)$，其中 $A_y$ 为 $y$ 的点权。 说起这道题，想起一张图（来自 $\text{hychyc}$ 巨佬的[主席树做法](https://www.luogu.com.cn/blog/hychyc/hnoi2015-kai-dian)）  （窝还是老老实实打点分树吧...）  #### **(1).【分析】** 统计贡献还是和模板题一样的套路，设： $f_1(i,j)=\sum_{x\in subtree(i),A_x\leqslant j}dis(x,i)$ $f_2(i,j)=\sum_{x\in subtree(i),A_x\leqslant j}dis(x,fa_i)$ 在查询点 $x$ 的答案时，上面只算了合法点到祖先的距离，漏掉了 $x$ 到 $fa_i$ 这一段，所以还要记点数： $g_1(i,j)=\sum_{x\in subtree(i),A_x\leqslant j}1$（这里就不需要设 $g_2$ 了，直接相减即可）。 查询时差分一下，只算权值小于等于 $k$ 的距离之和。 则有 $ans(x,k)=f_1(x,k)+$ $\sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)$ 其中 $G(i,fa_i)=$ $f_1(fa_i,k)-f_2(i,k)$ $+dis(x,fa_i)\times (g_1(fa_i,k)-g_1(i,k))$ 。 由于这题没有修改操作，所以直接在建虚树时开个 $\text{vector}$ 预排序，顺便求出前缀和，查询时二分位置即可。 另外，为减小常数可以把柿子拆开，在一次 $k$ 查询中对于虚树上每个祖先只使用一次二分。 空间复杂度：$O(n\log n)$ 。 时间复杂度：$O((n+q)\log^2 n)$ 。 #### **(2).【Code】** ```cpp struct QWQ{ int v;LL S1,S2;QWQ(Re V=0,LL s1=0,LL s2=0){v=V,S1=s1,S2=s2;} inline bool operator<(const QWQ &O)const{return v<O.v;} }; vector<QWQ>TR[N]; inline void getdis(Re x,Re fa,Re rt,Re d){ TR[rt].push_back(QWQ(A[x],d,Fa[rt]?Dis(x,Fa[rt]):0));//如果rt没有父亲就不要求dis了 for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,x,rt,d+a[i].w); } inline void sakura(Re x){ Re now=sum;vis[x]=1,getdis(x,0,x,0); sort(TR[x].begin(),TR[x].end());//预排序 for(Re i=1;i<now;++i)TR[x][i].S1+=TR[x][i-1].S1,TR[x][i].S2+=TR[x][i-1].S2;//前缀和 for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),Fa[rt]=x,sakura(rt); } inline QWQ get(Re x,Re K){//获取权值小于等于K的点信息之和 vector<QWQ>::iterator it=upper_bound(TR[x].begin(),TR[x].end(),QWQ(K)); if(it==TR[x].begin())return QWQ();--it;return QWQ((it-TR[x].begin())+1,it->S1,it->S2); } inline LL ask(Re x,Re K){//查询权值小于等于K的点与x的距离之和 QWQ TR=get(x,K);LL ans=TR.S1; if(Fa[x])ans-=TR.S2+(LL)Dis(x,Fa[x])*TR.v;//为迎合拆柿子,这里把第一次计算拿出来了 for(Re i=Fa[x];i;i=Fa[i]){ TR=get(i,K),ans+=TR.S1+(LL)Dis(x,i)*TR.v; if(Fa[i])ans-=TR.S2+(LL)Dis(x,Fa[i])*TR.v; } return ans; } ``` ### **3.【幻想乡战略游戏】** **[幻想乡战略游戏 $\text{[ZJOI2015] [P3345]}$](https://www.luogu.com.cn/problem/P3345)** **【题目大意】** 维护一颗带点权、边权树（树上点的度数不超过 $20$）。现有若干次修改点权的操作，每次操作结束后您需要选出一个核心点 $x$ 使得 $F(x)$ 最小，其中 $F(x)=\sum_{i=1}^{n}dis(x,i)\times A_i$，$A_i$ 为 $i$ 的点权。 #### **(1).【分析】** 这题关键在于分析性质~~猜结论~~。 假设当前核心为 $x$，将 $x$ 设为树的根，定义 $S_A(i)$ 为 $i$ 子树内所有点的点权之和。 对于 $x$ 的任意一个儿子节点 $y$，若将核心改为 $y$，那么 $\Delta F_{x \to y} =F(y)-F(x)=(S_A(x)-2S_A(y))\times dis(x,y)$ 。选 $y$ 更优当且仅当满足 $\Delta F_{x \to y}<0$ 即 $S_A(x)<2S_A(y)$，易知对于一个 $x$ 满足该式的 $y$ 最多只存在一个。 于是一个经过优化的暴力就产生了：每次询问从根开始，不断进入比它更优的儿子，如果找不到更优则说明本身已是最优。 但很多人只讲到这些就开始扯点分树信息维护了，实际上是不严谨的，我们还需要证明：“在以 $x$ 为根时，若 $y$ 没有 $x$ 优秀（表现为 $\Delta F_{x \to y}>0$），则 $y$ 子树里的点也一定没有 $x$ 优秀”。 > 设 $y$ 的儿子为 $y'$，考虑还是在以 $x$ 为根的前提下记算贡献： $\Delta F_{y \to y'}$ $=(S_A(y)-2S_A(y')+S_A(x)-S_A(y))\times dis(y,y')$ $=(S_A(x)-2S_A(y'))\times dis(y,y')$ 又因为 $S_A(y)\geqslant S_A(y')$（这题 $A_i$ 应该是不为负的，所以能得出这个关系式） 若 $\Delta F_{x \to y}>0$ 则 $S_A(x)>2S_A(y)\geqslant 2S_A(y')$ 因此 $\Delta F_{y \to y'}>0,$ $\Delta F_{x \to y'}=\Delta F_{x \to y}+\Delta F_{y \to y'}>0$ 。 证毕。 暴力单次询问复杂度 $O(20depth)$，而点分树有着 $depth=O(\log n)$ 的天然优势，我们可以把跳儿子的过程转移到点分树上进行。具体的说，从第一个重心开始，枚举它在原树上的儿子，若找到了比他更优的点，则跳到该子树（或者说子连通块）的重心。容易证明这样做一定不会错过最优解。 现在的问题只剩下快速计算 $F(x)$ 了，按照套路，设： $f_1(i)=\sum_{x\in subtree(i)}dis(x,i)\times A_x$ $f_2(i)=\sum_{x\in subtree(i)}dis(x,fa_i)\times A_x$ $g_1(i)=\sum_{x\in subtree(i)}A_x$ 则有 $F(x)=f_1(x)+$ $\sum_{i\in fatree(x),fa_i\neq 0} G(i,fa_i)$ 其中 $G(i,fa_i)=$ $f_1(fa_i)-f_2(i)$ $+dis(x,fa_i)\times (g_1(fa_i)-g_1(i))$ 。 由于这题的 $f_1,f_2,g_1$ 都只有一维，直接用数组存下来就好了。 空间复杂度：$O(n\log n)$ 。 时间复杂度：$O(n\log n+20q\log^2n)$ 。 （这题不知为啥常数小得惊人，不吸氧最慢的点只跑了 $900ms$） #### **(2).【Code】** ```cpp inline void change(Re x,Re v){//Sv即为g1 TR1[x]+=v*0,Sv[x]+=v; for(Re i=gs[x];i>=2;--i){ Re tmp=fdis[x][i-1]; TR1[frt[x][i-1]]+=(LL)v*tmp; TR2[frt[x][i]]+=(LL)v*tmp; Sv[frt[x][i-1]]+=v; } } inline LL ask(Re x){//计算F(x) LL ans=TR1[x]; for(Re i=gs[x];i>=2;--i){ Re tmp=fdis[x][i-1]; ans+=TR1[frt[x][i-1]]; ans-=TR2[frt[x][i]]; ans+=(LL)(Sv[frt[x][i-1]]-Sv[frt[x][i]])*tmp; } return ans; } inline LL find(Re x){ LL tmp=ask(x); for(Re i=T0.head[x];i;i=T0.a[i].next)//这里枚举原树 if(ask(T0.a[i].to)<tmp)return find(T0.a[i].rt);//如果to比x优秀就进入to所在连通块的重心（x在虚树上的儿子） return tmp; } ``` ### **4.【小清新数据结构题】** **[小清新数据结构题 $\text{[P3676]}$](https://www.luogu.com.cn/problem/P3676)** **【题目大意】** 维护一颗带点权树，需要支持两种操作：修改 $x$ 的点权，查询以点 $x$ 为根时的 $\sum_{i=1}^{n}(\sum_{j\in sub(i)}A_j)^2$，其中$A_j$ 为 $j$ 的点权，$sub(i)$ 为点 $i$ 子树内的节点集合。 #### **(1).【分析】** 一看就知道是个~~丧心病狂~~拆柿子题。 上公式（以 $x$ 为根）： 设 $sum=\sum_{i=1}^{n}A_i$，$S(i)=\sum_{j\in sub(i)}A_j$ $\sum_{i=1}^{n}S_i$ $=\sum_{i=1}^{n}A_i(dis(i,x)+1)$ $=sum+\sum_{i=1}^{n}dis(i,x)\times A_i$（每个点会在自己以及它的 $dis$ 个祖先处被统计到） 设 $F=\sum_{i=1}^{n}dis(i,x)\times A_i$（用与 [幻想乡战略游戏](https://www.luogu.com.cn/problem/P3345) 同样的方法可以求得） 由于 $\sum_{i=1}^{n}S_i(sum-S_i)$ 始终为一个定值（对于每条边 $x,y$，两边的连通块点权之和乘起来然后再求和），我们可以先 $O(n)$ 预处理出来，设为 $tmp$ 。 则 $ans(x)=\sum_{i=1}^{n}S_i^2$ $=sum\sum_{i=1}^{n}S_i-tmp$ $=sum(sum+F)-tmp$ 。 空间复杂度：$O(n\log n)$ 。 时间复杂度：$O((n+q)\log n)$ 。 #### **(2).【Code】** 代码就不放了，毕竟和上一道差不多，只是多了个 $dfs$ 预处理 $tmp$。  ### **5.【成都七中】** **[成都七中 $\text{[Ynoi2011] [P5311]}$](https://www.luogu.com.cn/problem/P5311)** **【题目大意】** 由一颗树，树上每个节点有一种颜色，每次查询给出 $l,r,x$，求保留树上编号在 $[l,r]$ 内的点，$x$ 所在联通块中颜色种类数。 #### **(1).【分析】** 这题比较难想。 先建出点分树，对于一次查询 $(l,r,x)$，在点分树上 $x$ 的祖先中找到深度最小的点 $pa$，且满足 $x$ 只经过编号 $[l,r]$ 内的点在原树上能到达 $pa$ 。记一下每个点 $i$ 到虚树祖先的路径上所经过的节点编号最小/大值就可以轻松求得（分别记为 $d_{min}(i,j)$ 和 $d_{max}(i,j)$）。 分析可知：$x$ 只经过编号 $[l,r]$ 内的点所在的连通块被完全包含在了 $subtree(pa)$ 中（虚子树）。我们把本次询问放到 $pa$ 节点处，最后再统一离线处理。 枚举虚树上的点 $rt$，处理该节点处的询问时，对于任意一个 $(l,r,x)$，满足 $l\leqslant d_{min}(i,rt)$ 且 $d_{max}(i,rt)\leqslant r$ 的 $i$ 即为与 $x$ 在同一连通块内的点，现需要统计这些点的颜色种类。 显然是个偏序问题，把询问和节点信息放一起按 $l$ 排序，指针从右往左扫，同时记录每种颜色节点右端点最小的位置，再开一棵树状数组维护每个位置上的数量，便可直接查询了。 空间复杂度：$O(n\log n)$ 。 时间复杂度：$O(n\log^2 n)$ 。 #### **(2).【Code】** ```cpp struct Query{int l,r,id,co;inline bool operator<(const Query &O)const{return l!=O.l?l>O.l:id<O.id;}};vector<Query>Q[N]; inline void getdis(Re x,Re rt,Re fa,Re d1,Re d2){//d1:最小值 d2:最大值 d1=min(d1,x),d2=max(d2,x),Q[rt].push_back((Query){d1,d2,0,A[x]}); frt[x][++gs[x]]=rt,fd1[x][gs[x]]=d1,fd2[x][gs[x]]=d2; for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x,d1,d2); } inline void change(Re x,Re l,Re r,Re id){//插入第id次询问l,r,x for(Re i=1;i<=gs[x];++i) if(l<=fd1[x][i]&&fd2[x][i]<=r){Q[frt[x][i]].push_back((Query){l,r,id,0});break;} } struct BIT{ int C[N]; inline void CL(Re x){while(x<=n)C[x]=0,x+=x&-x;} inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;} inline int ask(Re x){Re ans=0;while(x)ans+=C[x],x-=x&-x;return ans;} }TR; inline int GetAns(){ for(Re i=1;i<=100000;++i)mir[i]=inf; for(Re rt=1;rt<=n;++rt){//枚举点分树上的点 sort(Q[rt].begin(),Q[rt].end()); for(IT it=Q[rt].begin();it!=Q[rt].end();++it) if(it->id)Ans[it->id]=TR.ask(it->r);//查询 else if(it->r<mir[it->co])TR.add(mir[it->co],-1),TR.add(mir[it->co]=it->r,1);//节点信息，更新此颜色的最小右端点 for(IT it=Q[rt].begin();it!=Q[rt].end();++it) if(!(it->id))TR.CL(mir[it->co]),mir[it->co]=inf; } } ``` ### **6.【Iqea】** [$\text{Iqea}$](https://www.luogu.com.cn/problem/CF936E) [$\text{[CF936E]}$](http://codeforces.com/problemset/problem/936/E) **【题目大意】** 二维平面上给出若干个点的坐标，在这些点处打好地基（保证为一个四连通块，且不会出现封闭的空地）。有两种操作：在 $(x,y)$ 处建造商店，询问离 $(x,y)$ 最近的商店与 $(x,y)$ 的距离大小。两点距离定义为只经过有地基的点的最短路径长度，相邻两个格子距离为 $1$ 。保证每次给出的坐标处一定有地基。 #### **(1).【分析】** 一只神薙。 首先是非常巧妙的建图：每一行分开看，把同一行的若干个联通块分别缩成点，然后向四周相邻的点连边，由于没有封闭的空地，这样连出来一定是棵树。 支持加入关键点，查询距离最近的关键点，建点分树？ 似乎还没做完：两点之间的最短距离要如何在树上表示呢？ 看图：  任选 $a,b$ 路径上一个缩成点的小连通块 $m$ 作为中介（如图中黄色框），先分别求出 $a,b$ 移动到中介的最短路径 $d_a(m),d_b(m)$，并记录它们到达中介时的纵坐标 $y_a(m),y_b(m)$（在图中表现为 $1$ 号和 $8$ 号位置），则 $dis(a,b)=d_a(m)+d_b(m)+|y_a(m)-y_b(m)|$，即 $\min\{d_a(m)+d_b(m)+y_a(m)-y_b(m),d_a(m)+d_b(m)+y_b(m)-y_a(m)\}$ 。 现在点分树就可以轻松维护答案了，设： $f_1(i,j)=\sum_{x\in subtree(i),y_x(i)\leqslant j}d_x(i)-y_x(i)$ $g_1(i,j)=\sum_{x\in subtree(i),y_x(i)\geqslant j}d_x(i)+y_x(i)$ 则有 $ans(x,k)=$ $\min_{i\in fatree(x)}$ $\min\{d_x(i)+y_x(i)+f_1(i,y_x(i)),d_x(i)-y_x(i)+g_1(i,y_x(i))\}$ 二维的 $f_1,g_1$ 用树状数组维护。 空间复杂度：$O(n\log n)$ 。 时间复杂度：$O(n\log n+q\log^2 n)$ 。 #### **(2).【Code】** ```cpp int ip_O,n,o,x,y,T,op,MaxX,X[N],ip[N],Yl[N],Yr[N],idl[N],idr[N],head[N];vector<int>V[N];map<int,int>id[N]; struct QAQ{int to,next;}a[N<<1];//外层的这个是缩图所得到的树 inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} struct Tree{ int o,head[N]; struct QAQ{int to,next;}a[N<<2]; inline void add_(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;} inline void add(Re x,Re y){add_(x,y),add_(y,x);} }T0;//T0:以二维平面上的连通性建成的图 inline void get_tree(){//缩图建树 for(Re i=1;i<=n;++i)in(x),in(y),MaxX=max(MaxX,x),V[x].push_back(y),id[x][y]=i; for(Re x=1;x<=MaxX;++x)if(!V[x].empty()){ sort(V[x].begin(),V[x].end()); Re last=-1;idl[x]=ip_O+1; for(Re J=0,SZ=V[x].size(),y;J<SZ;last=V[x][J],++J){ if(last+1!=(y=V[x][J]))ip[id[x][y]]=++ip_O,X[ip_O]=x,Yl[ip_O]=Yr[ip_O]=y; else ip[id[x][y]]=ip_O,Yr[ip_O]=y,T0.add(id[x][y],id[x][y-1]); if(id[x-1].find(y)!=id[x-1].end())T0.add(id[x-1][y],id[x][y]); } idr[x]=ip_O; if(V[x-1].empty())continue; Re k=idl[x-1]; for(Re j=idl[x];j<=idr[x];++j){ while(k<=idr[x-1]&&Yr[k]<Yl[j])++k; for(Re k_=k;k_<=idr[x-1]&&Yl[k_]<=Yr[j];++k_)add(k_,j),add(j,k_); } } } struct QWQ{ int d,y;QWQ(Re D=0,Re Y=0){d=D,y=Y;} inline bool operator<(const QWQ &O)const{return d<O.d;} }; struct BIT{ int n,op;vector<int>C;//op=0:前缀 op=1:后缀(把询问、查询里的x都翻转一下就是了) inline void build(Re N){n=N,C.push_back(inf);while(N--)C.push_back(inf);}//这里就不用resize了,因为要初始化为inf inline void add(Re x,Re v){if(op)x=n-x+1;while(x<=n)C[x]=min(C[x],v),x+=x&-x;} inline int ask(Re x){if(op)x=n-x+1;Re ans=inf;while(x)ans=min(ans,C[x]),x-=x&-x;return ans;} }TR1[N],TR2[N]; int rt,sum,gs[N],vis[N],maxp[N],size[N],frt[N][22];QWQ fdis[N][22]; inline void getrt(Re x,Re fa){ size[x]=Yr[x]-Yl[x]+1,maxp[x]=0;//注意size的初始化不是1 for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa) getrt(to,x),size[x]+=size[to],maxp[x]=max(maxp[x],size[to]); maxp[x]=max(maxp[x],sum-size[x]);if(maxp[x]<maxp[rt])rt=x; } int Q[N],pan[N];QWQ dis[N]; inline void getdis0(Re rt){//bfs Re h=1,t=0; for(Re i=Yl[rt];i<=Yr[rt];++i)pan[Q[++t]=id[X[rt]][i]]=rt,dis[Q[t]]=QWQ(0,i-Yl[rt]+1); while(h<=t){ Re x=Q[h++]; for(Re i=T0.head[x],to;i;i=T0.a[i].next) if(pan[to=T0.a[i].to]!=rt&&!vis[ip[to]]) dis[to]=QWQ(dis[x].d+1,dis[x].y),pan[Q[++t]=to]=rt; } } inline void getdis(Re x,Re rt,Re fa){ frt[x][++gs[x]]=rt; for(Re i=Yl[x];i<=Yr[x];++i)fdis[id[X[x]][i]][gs[x]]=dis[id[X[x]][i]];//距离在bfs中已获得 for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]&&to!=fa)getdis(to,rt,x); } inline void sakura(Re x){ Re now=sum;vis[x]=1,getdis0(x),getdis(x,x,0); TR1[x].build(Yr[x]-Yl[x]+1),TR2[x].build(Yr[x]-Yl[x]+1),TR2[x].op=1;//树状数组的使用范围为[1,Yr-Yl+1] for(Re i=head[x],to;i;i=a[i].next)if(!vis[to=a[i].to]) sum=size[to]>size[x]?now-size[x]:size[to],maxp[rt=0]=inf,getrt(to,0),sakura(rt); } inline void change(Re y){ Re x=ip[y]; for(Re i=gs[x];i;--i) TR1[frt[x][i]].add(fdis[y][i].y,fdis[y][i].d-fdis[y][i].y), TR2[frt[x][i]].add(fdis[y][i].y,fdis[y][i].d+fdis[y][i].y); } inline int ask(Re y){ Re x=ip[y],ans=inf; for(Re i=gs[x];i;--i) ans=min(ans,fdis[y][i].d+fdis[y][i].y+TR1[frt[x][i]].ask(fdis[y][i].y)), ans=min(ans,fdis[y][i].d-fdis[y][i].y+TR2[frt[x][i]].ask(fdis[y][i].y)); return ans; } ``` ### **7.【大毒瘤】** ~~相信您已经积累了足够的实力，下面我们来看一道果题吧QAQ~~ [**紫荆花之恋** $\text{[WC2014] [P3920]}$](https://www.luogu.com.cn/problem/P3920) [](https://www.luogu.com.cn/problem/P3920) ## **四：【总结】** 模板及例题 $1.1,1.2$ 都是靠数据结构维护贡献，例 $2$ 则换成了 $\text{STL}$ 。套娃行为所导致的的码量增加以及大常数都是值得关注的问题。 例 $3,4$ 主要是按照容斥套路推式子，相对比较好掌握，但细节较多，要注意统计贡献时补充不漏。 例 $5$ 难点在于利用点分树的特殊性质转离线。点分树各种神奇的特性，对应到不同的题上就会有各种神奇的解法。如果没有强大的~~瞎蒙~~猜结论能力，就多刷刷题吧，见多识广总没有坏处的。 例 $6$ 不光要会神仙建图，还要想办法用点分树能维护的东西来表示两点距离。这道题有效地提醒了我们：点分树有着不错的灵活性，并非只有那个一成不变的模板，所以不要死记硬背啊... >Q: 话说点分树能搞可持久化吗？ A: 虽然听起来比较毒瘤，但不瞒您说，还真可以（具体见 [可持久化点分树](https://www.cnblogs.com/Khada-Jhin/p/10175454.html)） ## **五：【参考资料】** - **[震波 题解 $\text{by Enigma-aw}$](https://www.cnblogs.com/enigma-aw/p/6209545.html)** - **[开店 题解 $\text{by shadowice1984}$](https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p3241)** - **[$\text{Iqea}$ 题解 $\text{by Dream-Lolita}$](https://blog.csdn.net/dream_lolita/article/details/84900147)** - **[可持久化点分树 $\text{by JhinLZH}$](https://www.cnblogs.com/Khada-Jhin/p/10175454.html)**