最近刚刚讲了树链剖(pōu)分，练了几道题，也该来个小结了。
事实上，树链剖分就是把树切成几条链，再套上一个数据结构罢了。这样子有个好处，就是可以高效地完成在树上的一些操作。
剖分的方法：
随机剖分
盲目剖分
启发式剖分
从名字上看，明显启发式剖分是最佳选择（= =）所谓启发式剖分，就是重链剖分。
先看两个概念：
重边：树中父节点连接儿子中size（即以它为根的子树的结点个数）最大的一条边。
轻边：非重边。
重链：全部由重边组成的一条链（包括一个点）。
重链剖分就是将整颗树剖分成几条重链。
（为什么这样最优？见1.）
可以用来对一条路径上的一些信息进行操作，例如单点/区间修改，第k大的查询
等，可以根据不同的操作，选择不同的数据结构（如线段树，平衡树）。
无法动态地删除/插入新的边。（如果想实现，可以用动态树）
这个有两种实现方法一种是套上一个数据结构，一种是套上几个数据结构。
这里详细介绍下第一种（由cxjyxx_me大牛自创），第二种请见Xietutu's blog.
先找到重边，过程中，如果确定出一条轻边就以其为根建成一条链，接着建成一个数据结构（例如线段树，平衡树），最后在来一次以1为根的build_chain即可。
因此这样做会建出好几颗树。不过效率会提高许多。有图为证http://www.lydsy.com/JudgeOnline/problemstatus.php?id=2243&page=0
//伪代码 by Lazycal build_chain(x) k=0 while exists x save the node x update x's chain_head update x's root // such as segment tree or balanced tree x=x's child which has maximal size build_tree // segment tree or balanced tree ======================================================== dfs(k) for each edge (u,k) in V and not vis[u] dfs(k); update k.size if u.size>max.size build_chain(max) else build_chain(u)
对于u,v:
1.当u与v在同一重链时，直接在数据结构里面查询/修改，break。
2.当u与v不同重链时，先取出重链头比较靠下的（设为u），然后查询/修改u与u's chain_head, the father of u's chain_head->u。
如此往复。
1.证明如下：可以这么理解（个人浅见），设x为p的轻边所连的孩子，则x.size<p.size/2（为什么？请读者自己想想，很简单的），这样一来，任意一条链的轻边个数不超过log(n)，所以重链数自然也不会超过log(n)，于是u到v最坏情况是u走上去到某个点再折下来到v，但即使如此对于数据结构的询问次数也不超过log(n)次，而每次数据结构的询问时间为log(n)，于是复杂度便可视为O(log(n)^2)。
1.bzoj1036(模板)
//linenums won't be copied
#include <cstdio> #include <algorithm> const int N=30000+9; struct node { int lc,rc,max,sum,l,r; node (const int a=0,const int b=0,const int c=0, const int d=0,const int e=0,const int f=0): lc(a),rc(b),max(c),sum(d),l(e),r(f){} }a[N*4]; struct Point { int seg_root,head,value,max,d,size,p; }p[N]; struct info { int next,link; }es[N*2]; int n,q,son[N],nt,ec,t[N]; char s[10]; inline int lef(int x){return a[x].lc;} inline int rig(int x){return a[x].rc;} void addedge(int x,int y) { es[++ec].next=son[x]; son[x]=ec; es[ec].link=y; } int build_tree(int l,int r) { ++nt; if (l==r) { a[nt]=node(0,0,p[t[l]].value,p[t[l]].value,l,r); return nt; } int index=nt,lc=build_tree(l,(l+r)/2), rc=build_tree((l+r)/2+1,r); a[index]=node(lc,rc,std::max(a[lc].max,a[rc].max),a[lc].sum+a[rc].sum,l,r); return index; } void build_chain(int x) { int k=0,root=x; while (x) { p[x].seg_root=nt+1; p[x].head=root; t[++k]=x; x=p[x].max; } build_tree(1,k); } void tr(int x,int d,int fa) { p[x].d=d;p[x].size=1; for (int i=son[x];i;i=es[i].next) if (es[i].link!=fa) { int u=es[i].link; tr(u,d+1,x); p[u].p=x; p[x].size+=p[u].size; if (p[u].size>p[p[x].max].size) { if (p[x].max) build_chain(p[x].max); p[x].max=u; }else build_chain(u); } } void modify(int index,int v,int pos,int x) { int k=0; while (a[index].l!=a[index].r) { a[index].sum+=v-p[x].value; t[++k]=index; int mid=(a[index].l+a[index].r)>>1; if (pos<=mid) index=a[index].lc; else index=a[index].rc; } p[x].value=a[index].sum=a[index].max=v; while (k--) a[t[k+1]].max=std::max(a[lef(t[k+1])].max,a[rig(t[k+1])].max); } void seg_query(int L,int R,int &res,int tag,int index) { int l=a[index].l,r=a[index].r,mid=(l+r)>>1; if (L<=l && r<=R) { res=tag?res+a[index].sum:std::max(a[index].max,res); return; } if (L<=mid) seg_query(L,R,res,tag,lef(index)); if (mid< R) seg_query(L,R,res,tag,rig(index)); } int query(int u,int v,int tag) { int res=tag?0:-0x7fffffff; while (p[u].head!=p[v].head) { if (p[p[u].head].d<p[p[v].head].d) std::swap(u,v); seg_query(1,p[u].d-p[p[u].head].d+1,res,tag,p[u].seg_root); u=p[p[u].head].p; } if (p[u].d>p[v].d) std::swap(u,v); seg_query(p[u].d-p[p[u].head].d+1, p[v].d-p[p[v].head].d+1, res,tag,p[u].seg_root); return res; } int main() { #ifndef ONLINE_JUDGE freopen("1036.in","r",stdin); freopen("1036.out","w",stdout); #endif int x,y; scanf("%d",&n); for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } for (int i=1;i<=n;++i) scanf("%d",&p[i].value); tr(1,1,0); build_chain(1); scanf("%d\n",&q); while (q--) { scanf("%s",s); if (s[0]=='Q' && s[1]=='M') { scanf("%d%d\n",&x,&y); printf("%d\n",query(x,y,0));//0: max }else if (s[0]=='Q' && s[1]=='S') { scanf("%d%d",&x,&y); printf("%d\n",query(x,y,1));//1: sum }else { scanf("%d%d\n",&x,&y); modify(p[x].seg_root,y,p[x].d-p[p[x].head].d+1,x); } } }2.bzoj2243(模板，注意处理两条重链的连接处)
//linenums won't be copied
#include <cstdio> #include <algorithm> const int N=100000+9; struct point { int value,seg_root,head,max,size,d,p; }p[N]; struct Triple { int num,lcol,rcol; Triple (const int a=0,const int b=0,const int c=0): num(a),lcol(b),rcol(c){} }; struct node { int lc,rc,tag,lcol,rcol,num,l,r; node (const int a=0,const int b=0,const int c=0,const int d=0, const int e=0,const int f=0,const int g=0,const int h=0): lc(a),rc(b),tag(c),lcol(d),rcol(e),num(f),l(g),r(h){} }a[N*2]; struct info { int next,link; }es[N*2]; int n,m,nt,son[N],col,t[N],ec; inline int lef(int index) {return a[index].lc;} inline int rig(int index) {return a[index].rc;} inline int getindex(int u) {return p[u].d-p[p[u].head].d+1;} int build(int l,int r) { int index=++nt; if (l==r) a[index]=node(0,0,p[t[l]].value,p[t[l]].value,p[t[l]].value,1,l,r); else { int lc=build(l,(l+r)>>1),rc=build(((l+r)>>1)+1,r); a[index]=node(lc,rc,0,a[lc].lcol,a[rc].rcol, a[lc].num+a[rc].num-(a[lc].rcol==a[rc].lcol),l,r); } return index; } void build_chain(int x) { int k=0,root=x; while (x) { p[x].seg_root=nt+1; p[x].head=root; t[++k]=x; x=p[x].max; } build(1,k); } void tr(int x,int d) { p[x].d=d; p[x].size=1; for (int i=son[x];i;i=es[i].next) if (es[i].link!=p[x].p) { int u=es[i].link; p[u].p=x; tr(u,d+1); p[x].size+=p[u].size; if (p[u].size>p[p[x].max].size) { if (p[x].max) build_chain(p[x].max); p[x].max=u; }else build_chain(u); } } void pushdown(int index) { int l=lef(index),r=rig(index); a[l].tag=a[l].lcol=a[l].rcol=a[index].tag; a[r].tag=a[r].lcol=a[r].rcol=a[index].tag; a[l].num=a[r].num=1; a[index].tag=0; } void tree_modify(int index,int L,int R) { int l=a[index].l,r=a[index].r,mid=(l+r)>>1; if (L<=l && r<=R) { a[index].tag=a[index].lcol=a[index].rcol=col; a[index].num=1; return; } if (a[index].tag) pushdown(index); if (L<=mid) tree_modify(lef(index),L,R); if (mid<R) tree_modify(rig(index),L,R); a[index].tag=0; l=lef(index);r=rig(index); a[index].lcol=a[l].lcol; a[index].rcol=a[r].rcol; a[index].num=a[l].num+a[r].num-(a[l].rcol==a[r].lcol); } Triple tree_query(int index,int L,int R) { int l=a[index].l,r=a[index].r,mid=(l+r)>>1,lcol=-1,rcol=-1; if (L<=l && r<=R) return Triple(a[index].num,a[index].lcol,a[index].rcol); if (a[index].tag) pushdown(index); int res=0,count=0; Triple lc,rc; if (L<=mid) { ++count; lc=tree_query(lef(index),L,R); res+=lc.num; lcol=lc.lcol,rcol=lc.rcol; } if (mid< R) { ++count; rc=tree_query(rig(index),L,R); res+=rc.num; if (lcol==-1) lcol=rc.lcol; rcol=rc.rcol; } res-=(count==2 && a[lef(index)].rcol==a[rig(index)].lcol); return Triple(res,lcol,rcol); } void modify(int u,int v) { while (p[u].head!=p[v].head) { if (p[p[u].head].d<p[p[v].head].d) std::swap(u,v); tree_modify(p[u].seg_root,1,getindex(u)); u=p[p[u].head].p; } if (p[u].d>p[v].d) std::swap(u,v); tree_modify(p[u].seg_root,getindex(u),getindex(v)); } int query(int u,int v) { int res=0,lcolu=-1,lcolv=-1; while (p[u].head!=p[v].head) { if (p[p[u].head].d<p[p[v].head].d) std::swap(u,v),std::swap(lcolu,lcolv); Triple tmp=tree_query(p[u].seg_root,1,getindex(u)); res+=tmp.num-(tmp.rcol==lcolu); //printf("%d ",res); lcolu=tmp.lcol; u=p[p[u].head].p; } if (p[u].d>p[v].d) std::swap(u,v),std::swap(lcolu,lcolv); Triple tmp=tree_query(p[u].seg_root,getindex(u),getindex(v)); res+=tmp.num-(tmp.rcol==lcolv)-(tmp.lcol==lcolu); //printf("%d\n",res); return res; } inline void addedge(int x,int y) { es[++ec].next=son[x]; son[x]=ec; es[ec].link=y; } int main() { #ifndef ONLINE_JUDGE freopen("2243.in","r",stdin); freopen("2243.out","w",stdout); #endif scanf("%d%d",&n,&m); int x,y; for (int i=1;i<=n;++i) scanf("%d",&p[i].value); for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } tr(1,1); build_chain(1); scanf("\n"); while (m--) { char c; scanf("%c",&c); if (c=='C') { scanf("%d%d%d\n",&x,&y,&col); modify(x,y); }else { scanf("%d%d\n",&x,&y); printf("%d\n",query(x,y)); } } }3.bzoj1146 (区间第k大查询，有点难，需要树套树，注意二分)
//linenums won't be copied
/************************************************************** Problem: 1146 User: lazycal Language: C++ Result: Accepted Time:15296 ms Memory:49280 kb ****************************************************************/ #include <cstdio> #include <algorithm> const int N=80000+9; struct node { int l,r,key,size,p; node (const int a=0,const int b=0,const int c=0, const int d=0,const int e=0): l(a),r(b),key(c),size(d),p(e){} }a[2000000]; struct seg_node { int l,r,root,lc,rc,head_index; seg_node (const int a=0,const int b=0,const int c=0, const int d=0,const int e=0,const int f=0): l(a),r(b),root(c),lc(d),rc(e),head_index(f){} }sn[N*2]; struct point { int d,size,time,seg_root,head,max,p; }p[N]; struct edge { int link,next; }es[N*2]; int n,q,ec,son[N],nbt,nst,t[N]; inline int lef(int x){return sn[x].lc;} inline int rig(int x){return sn[x].rc;} inline int getindex(int x){return p[x].d-p[p[x].head].d+1;} inline void addchild(int p,int y,int x) { if (a[p].l==x) a[p].l=y; else a[p].r=y; } inline void rig_rotate(int x) { int y=a[x].l; a[y].p=a[x].p; a[x].p=y; a[a[y].r].p=x; addchild(a[y].p,y,x); a[x].l=a[y].r; a[y].r=x; a[y].size=a[x].size; a[x].size=a[a[x].l].size+a[a[x].r].size+1; } inline void lef_rotate(int x) { int y=a[x].r; a[y].p=a[x].p; a[x].p=y; a[a[y].l].p=x; addchild(a[y].p,y,x); a[x].r=a[y].l; a[y].l=x; a[y].size=a[x].size; a[x].size=a[a[x].l].size+a[a[x].r].size+1; } inline void splay(int x,int par,int &root) { while (a[x].p!=par) { int y=a[x].p,z=a[y].p; if (z!=par && a[y].l==x && a[z].l==y) rig_rotate(z),rig_rotate(y); else if (z!=par && a[y].r==x && a[z].r==y) lef_rotate(z),lef_rotate(y); else if (a[y].l==x) rig_rotate(y); else lef_rotate(y); } if (!par) root=x; } void insert(int x,int &root,int Index) { int index=root,par=0; while (index) { ++a[index].size; if (a[index].key<x) par=index,index=a[index].l; else par=index,index=a[index].r; } a[Index]=node(0,0,x,1,par); if (a[par].key<a[Index].key) a[par].l=Index; else a[par].r=Index; splay(Index,0,root); } int build_bal_tree(int l,int r) { int root=++nbt; a[nbt]=node(nbt+1,0,-0x7fffffff,2,0); ++nbt; a[nbt]=node(0,0,0x7fffffff,1,nbt-1); for (int i=l;i<=r;++i) insert(p[t[i]].time,root,++nbt); return root; } int build_seg_tree(int l,int r) { int index=++nst; if (l==r) { sn[index]=seg_node(l,r,build_bal_tree(l,r),0,0,nbt+3); return index; } int lc=build_seg_tree(l,(l+r)>>1), rc=build_seg_tree(((l+r)>>1)+1,r); sn[index]=seg_node(l,r,build_bal_tree(l,r),lc,rc,nbt+3); return index; } void build_chain(int x) { int k=0,root=x; while (x) { p[x].seg_root=nst+1; p[x].head=root; t[++k]=x; x=p[x].max; } build_seg_tree(1,k); } void tr(int x,int d) { p[x].d=d;p[x].size=1; for (int i=son[x];i;i=es[i].next) if (es[i].link!=p[x].p) { int u=es[i].link; p[u].p=x; tr(u,d+1); p[x].size+=p[u].size; if (p[u].size>p[p[x].max].size) { if (p[x].max) build_chain(p[x].max); p[x].max=u; }else build_chain(u); } } int bal_rank(int k,int index) { ++k; while (k!=a[a[index].l].size+1) if (k>a[a[index].l].size) k-=a[a[index].l].size+1,index=a[index].r; else index=a[index].l; return index; } int bal_query(int x,int index) { int res=0; while (index) if (x<a[index].key) res+=1+a[a[index].l].size,index=a[index].r; else index=a[index].l; --res; return res; } void remove(int &root,int index) { splay(index,0,root); int pred=a[index].l,succ=a[index].r; while (a[pred].r) pred=a[pred].r; while (a[succ].l) succ=a[succ].l; splay(pred,0,root);splay(succ,root,root); --a[root].size;--a[a[root].r].size; a[a[root].r].l=0; } void modify(int x,int y) { int seg_index=p[x].seg_root,index=getindex(x); while (seg_index) { int &root=sn[seg_index].root; remove(root,index-sn[seg_index].l+sn[seg_index].head_index); insert(y,root,index-sn[seg_index].l+sn[seg_index].head_index); //print(seg_index); int mid=(sn[seg_index].l+sn[seg_index].r)>>1; if (index<=mid) seg_index=sn[seg_index].lc; else seg_index=sn[seg_index].rc; } p[x].time=y; } int seg_query(int index,int L,int R,int x) { int l=sn[index].l,r=sn[index].r,mid=(l+r)>>1,res=0; if (L<=l && r<=R) return bal_query(x,sn[index].root); if (L<=mid) res+=seg_query(lef(index),L,R,x); if (mid< R) res+=seg_query(rig(index),L,R,x); return res; } int rank(int x,int u,int v) { int res=0; while (p[u].head!=p[v].head) { if (p[p[u].head].d<p[p[v].head].d) std::swap(u,v); res+=seg_query(p[u].seg_root,1,getindex(u),x); u=p[p[u].head].p; } if (p[u].d>p[v].d) std::swap(u,v); res+=seg_query(p[u].seg_root,getindex(u),getindex(v),x); return res; } void query(int k,int u,int v) { int l=-2,r=100000009; while (l+1<r) { int mid=(l+r)>>1; if (rank(mid,u,v)<=k-1) r=mid; else l=mid; } if (l==-2) puts("invalid request!"); else printf("%d\n",r); } inline void addedge(int x,int y) { es[++ec].next=son[x]; son[x]=ec; es[ec].link=y; } int main() { #ifndef ONLINE_JUDGE freopen("1146.in","r",stdin); freopen("1146.out","w",stdout); #endif scanf("%d%d",&n,&q); for (int i=1;i<=n;++i) scanf("%d",&p[i].time); int x,y,k; for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } tr(1,1); build_chain(1); while (q--) { scanf("%d%d%d",&k,&x,&y); if (!k) modify(x,y); else query(k,x,y); } }转载于:https://www.cnblogs.com/lazycal/archive/2013/01/16/2862177.html
相关资源：JAVA上百实例源码以及开源项目