树链剖分讲义

　　树链剖分 【是什么】 顾名思义，树链剖分就是把一棵树剖分成许多链。 树链，即为树上的路径，而剖分，就是指把树化成多个区间，化成许多线； 【干什么】 如果要维护树形结构上的数据，怎么办？ 如果是不更改的值可以直接用ST，或者前缀和等方式。 如果要修改值呢？ 如果修改的不止是单点呢？ 如果询问的不止是最值呢？ 如果修改不止涉及子树而是还有路径呢？ 综上所述，我们需要一种高效而且通用的算法——树链剖分。 树链剖分可以将树形结构转化为线形，然后使用最好的数据结构进行优化【树状数组 线段树 平衡树etc】 当然比较常用的是线段树。 【思想】 划分有多种形式，其他不提。只讲轻重划分。 轻重划分，就是划分的时候，有轻重两种链。 重链就是对于每一个节点来说，其子节点最多的一条边，这条边连着的点是重儿子。 除了对于每一个节点唯一的重链重儿子以外，其余都是轻儿子和轻链。 所以为了求出这些重链重儿子，我们需要进行预处理。 预处理使用两边dfs（dfs相对好写，一般也不会爆栈，如果数据量比较神奇请自行根据dfs改成bfs就行了。） 首先，我们必须明确各个变量： size【即该结点的子结点数目】 son【即重儿子】 fa【父亲结点】 top【所在重链的顶端】 dep【深度】 w【当前结点在所维护的线状数据结构中的位置】 第一遍： 求出每一个节点的 fa son size dep 第二遍： 求出 top与 w 【在此，我们必须了解，对于每一个重儿子 其top必然是其父亲的top； 并且我们由于要维护树，所以在位置上也要将重链都放在一起，也就是说在我们维护的数据结构中，重链是不可以断开存储的。 同时，对于每一个轻儿子，其top值都是本身】 处理出这些之后，我们就可以根据w数组来讲数据加入数据结构了。 数据结构自己根据喜好选择就行了... 之后再讲怎么进行更新与求值。 子树的更新： 需要引入end数组记录每一个结点的子节点究竟在 哪里结束，然后直接求值与更新就可以了。 路径更新： 与倍增的lca有一点相似...当然也有多种方法。 只讲一种。 对于 u v两个结点 我们分别记录其top 为f1 f2 若f1 f2相等 则说明在同一重链上 也就是他们的维护是连续的，直接修改就行了。 如果不相等呢？ 那么他们肯定不是同一重链上了，那么我们就应该找到他们的最近公共祖先。然后更新，对吧？ 所以我们找到 f1 f2中dep最大的，然后更新其到x或y的一段，之后将x或者y换成其父亲。 然后一直重复知道f1与f2相等，再进行第一个的操作。 这里我出示一个例子： （2） 【

　　应用】 在应用的时候，可能需要维护的是结点值或者边权，如果是边权的话，我们应该选择把边权挪到点上并且记录位置。 【例题】 维护点： hdu3966： /* 树链剖分裸题 其实就是维护点值 然后查询每个点的值 个人感觉dfs重标号并且记录 直接上树状数组 毫无压力... 不过还是练习一下树链剖分比较好 虽然我依然不想放弃树状数组....决定用树状数组搞... */ #pragma comment(linker, /STACK:1024000000,1024000000) #includecstdio #includecstring using namespace std; const int N=1000005; const int INF=(1 struct data{ int to,next; }e[N]; int head[N],gs; int son[N],size[N],top[N],w[N],fa[N],dep[N],cntw,n,m,p; int tr[N],vv[N]; void add(int fr,int to) { gs++;e[gs].next=head[fr];e[gs].to=to;head[fr]=gs; } int lowbit(int x) { return x } void add1(int k,int x) { while(k=n) { tr[k]+=x; k+=lowbit(k); } } int sum1(int x) { int tot=0; while(x0) { tot+=tr[x]; x-=lowbit(x); } return tot; } void dfs1(int u,int fat,int d) { dep[u]=d; size[u]=1; fa[u]=fat; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fat) { dfs1(v,u,d+1); size[u]+=size[v]; if(son[u]==-1||size[v]size[son[u]]) son[u]=v; } } } void dfs2(int u,int tp) { w[u]=++cntw; top[u]=tp; // add1(cntw,v[u]);add1(cntw+1,-v[u]); if(son[u]==-1) return ; dfs2(son[u],tp); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa[u]v!=son[u]) dfs2(v,v); } } void swap(int x,int y) { int t=x;x=y;y=t; } void lca(int x,int y,int delt) { int f1=top[x],f2=top[y]; while(f1!=f2) { if(dep[f1]dep[f2]) { swap(f1,f2); swap(x,y); } add1(w[f1],delt); add1(w[x]+1,-delt); x=fa[f1]; f1=top[x]; } if(dep[x]dep[y]) swap(x,y); add1(w[x],delt); add1(w[y]+1,-delt); return ; } int main() { // freopen(1.txt,r,stdin); // freopen(11.txt,w,stdout); int a,b,c; while(scanf(%d%d%dn,p)!=EOF) { memset(head,0,sizeof(head)); memset(son,-1,sizeof(son)); memset(tr,0,sizeof(tr)); cntw=0;gs=0; for(int i=1;i++i) scanf(%dvv[i]); for(int i=1;i++i) { scanf(%d%da, add(a,b); add(b,a); } dfs1(1,0,0); dfs2(1,1); for(int i=1;i++i) { add1(w[i],vv[i]); add1(w[i]+1,-vv[i]); } char tmp[10]; for(int i=1;i++i) { scanf(%s if(tmp[0]=='I') { scanf(&quo t;%d%d%da,c); lca(a,b,c); } if(tmp[0]=='D') { scanf(%d%d%da,c); lca(a,b,-c); } if(tmp[0]=='Q') { scanf(%da); int ans=sum1(w[a]); printf(%dn } } } return 0; } bzoj4034【2015河南省

　　选】： /* 其实区间也就是从结点到根... 注意维护的是点权 1单点修改 2区间修改 3区间求和 树链剖分 + 树状数组 ...数据要开long long */ #includecstdio #includecstring using namespace std; #define ll long long const int N=100005; struct data{ int to,next; }e[N int head[N],gs; void adde(int fr,int to) { gs++;e[gs].to=to;e[gs].next=head[fr];head[fr]=gs; } int son[N],size[N],fa[N],top[N],w[N],end[N],n,m; ll tr[2][N],cntw,va[N]; int read() { int x=0,fu=1; char ch=getchar(); while (ch'0' || ch'9'){ if (ch=='-') fu=-1; ch=getchar(); } while (ch='0' ch='9'){ x=x*10+ch-'0'; ch=getchar(); } return x*fu; } int lowbit(int x) { return x } void add(int m,int k,ll x) { while(k=n) { tr[m][k]+=x; k+=lowbit(k); } } ll sum(int m,int k) { ll tot=0; while(k) { tot+=tr[m][k]; k-=lowbit(k); } return tot; } void change(int l,int r,ll delt) { add(0,l,-(l-1)*delt); add(1,l,delt); add(0,r+1,r*delt); add(1,r+1,-delt); } void dfs1(int u,int fat) { fa[u]=fat; size[u]=1; // son[u]=-1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa[u]) { dfs1(v,u); size[u]+=size[v]; if(size[v]size[son[u]]) son[u]=v; } } } //估计之前一直不过的原因...是这里的son各种更新出现了混乱 void dfs2(int u,int tp) { top[u]=tp; w[u]=++cntw; // change(w[u],w[u],va[u]); if(son[u]) dfs2(son[u],tp); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa[u]v!=son[u]) dfs2(v,v); } end[u]=cntw; } //0是原数组 1是delt ll getsum(int l,int r) { return sum(0,r)+sum(1,r)*r-sum(0,l-1)-sum(1,l-1)*(l-1); } ll lcaask(int x) { ll sum=0; while(x) { sum+=getsum(w[top[x]],w[x]); x=fa[top[x]]; } return sum; } int main() { // freopen(1.txt,r,stdin); // freopen(11.txt,w,stdout); int a,b; ll c; n=read();m=read(); for(int i=1;i++i) va[i]=read(); for(int i=1;i++i) { a=read();b=read(); adde(a,b);adde(b,a); } dfs1(1,0); dfs2(1,1); for(int i=1;i++i) change(w[i],w[i],va[i]); for(int i=1;i++i) { a=read(); if(a==1) { b=read();c=read(); change(w[b],w[b],c); } if(a==2) { b=read();c=read(); change(w[b],end[b],c); } if(a==3) { b=read(); printf(%l ldn,lcaask(b)); } } return 0; } 维护边： poj2763： /* 树链剖分 然后线段树解决 其实修改是单点的...但是解决就比较...恶心了... 理论上来说可以用树链剖分加上树状数组解决 维护的是边而不是点 然后把每一个 边的权值赋给终点 之后维护每一个点的权值 修改是单点 然后计算的是区间和 */ #includecstdio #includecstring using namespace std; const int N=100005; st

　　ruct data{ int to,next,id; }e[N*2]; int head[N],gs; int dep[N],size[N],top[N],son[N],fa[N],w[N],cntw,va[N],n,m; int tr[N],pos[N]; void adde(int fr,int to,int id) { gs++;e[gs].to=to;e[gs].next=head[fr];head[fr]=gs;e[gs].id=id; } int lowbit(int x) { return x } void add(int k,int x) { while(k=n) { tr[k]+=x; k+=lowbit(k); } } int sum(int k) { int tot=0; while(k) { tot+=tr[k]; k-=lowbit(k); } return tot; } void dfs1(int u,int fat) { dep[u]=dep[fat]+1; fa[u]=fat; size[u]=1; son[u]=-1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fat) { pos[e[i].id]=v; dfs1(v,u); size[u]+=size[v]; if(size[v]size[son[u]]||son[u]==-1) son[u]=v; } } } void dfs2(int u,int tp) { top[u]=tp; w[u]=++cntw; if(son[u]==-1) return ; dfs2(son[u],tp); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa[u]v!=son[u]) dfs2(v,v); } } void swap(int x,int y) { int t=y;y=x;x=t; } int lca(int x,int y) { int tot=0; int f1=top[x],f2=top[y]; while(f1!=f2) { if(dep[f1]dep[f2]) { swap(f1,f2); swap(x,y); } tot+=sum(w[x])-sum(w[f1]-1);//在维护边的情况下 这里也是直接用w[f1]-1的 // 因为下一个会直接跳到其父亲... x=fa[f1]; f1=top[x]; } if(x==y) return tot; if(dep[x]dep[y]) swap(x,y); tot+=sum(w[y])-sum(w[son[x]]-1); //同理由于维护边 所以这里也是要用son也就是重儿子的位置减去的 其实和-1没有区别。 return tot; } int main() { // freopen(1.txt,r,stdin); // freopen(11.txt,w,stdout); int a,b,c,tmp,q,s; while(scanf(%d%d%dn,s)!=EOF) { memset(head,0,sizeof(head)); memset(tr,0,sizeof(tr)); gs=0,cntw=0; for(int i=1;i++i) { scanf(%d%d%da,va[i]); adde(a,b,i);adde(b,a,i); } dfs1(1,0); dfs2(1,1); for(int i=1;i++i) add(w[pos[i]],va[i]); for(int i=1;i++i) { scanf(%dtmp); if(tmp==0) { scanf(%da); printf(%dn&q uot;,lca(s,a)); s=a; } else { scanf(%d%da, add(w[pos[a]],b-va[a]); //这个地方我居然...写了个i... va[a]=b; } } } return 0; } 但是总结来说，树链剖分虽然代码量惊人了一些 【因为要写两个dfs还有数据结构】，但是一般出题都是可以看出来的。 就是说只要涉及到树上动态操作的，毫无疑问写树链剖分吧...虽然大部分时间noip用不到，但是2015noip day2 T3就可以用树链剖分解决。