好久没打博客了。。。。。。。。。狗出竞赛。。。
这东西网上大佬们许多解释，我也只是记录自己的学习而已。虽然说连一道题都没有AC_ (:зゝ∠)_。 推荐就不拉网址了，那个新浪博客st开头的作者写的挺好的。
关于树链剖分，说白了就是树上的区间操作，把Segement Tree，BIT,平衡树套在树上而已，只是简单想想思路。
树链剖分，自然而然就是将一棵树进行剖解，把其分解成许多条链，对于每一条链都进行重编号然后用一个数据结构去维护。
首先对这一棵树进行链条预处理。 我们规定size[x]表示x为根的子树的大小，那么对于一个节点u，它的重儿子就是它儿子中 size 最大的儿子（如果有同样大的就任选一个），父亲与重儿子的连边称为重边。其他的儿子就被称为轻儿子，轻边定义如上。 就有第一个性质：size[x]<2*size[light_son]。 我们再定义重链指重边组成的链，轻链同理。某个链的第一个节点叫链顶 就有第二个性质：根到某一点的重链吗，轻链的个数都不超过 log2n 个。
我们用以下数组去维护 size[x]表示x为根的子树节点数。 son[x]表示x的重儿子的编号。 top[x]表示x的x所在链的链顶的编号 deep[x]表示x的深度（根为1） dad[x]表示x的父亲编号 id[x]表示x的重编号（可以是点或边）
可以两个dfs求出来： 1.可以先求出：size,son,deep,dad。
void dfs1(int x,int fa,int dep) { dad[x]=fa; size[x]=1; deep[x]=dep; int big=0; for(int i=fre[x];i;i=nnnn[i]){ if (go[i]==fa) continue; dfs1(go[i],x,dep+1); if (size[go[i]]>big) son[x]=go[i],big=size[go[i]]; size[x]+=size[go[i]]; } }2.对于top，我们可以发现，对于一个点u，有top[son[u]]=top[u]，轻儿子x的有top[x]=x。 对于id，直接加就好了。我们dfs的顺序是先是先遍历完一棵子树的重链的，所以重链（重链所连的点）的id是连续的一段，正好可以用数据结构维护。
void dfs2(int x,int tp) { id[x]=++tot; top[x]=tp; now[tot]=a[x]; if (son[x]!=-1) dfs2(son[x],tp); for(int i=fre[x];i;i=nnnn[i]){ if (go[i]==son[x]) continue; if (go[i]==dad[x]) continue; dfs2(go[i],go[i]); } }然后id的编号弄入一个新数组里（上面是now）。 然后就是对于now的数据结构维护了
假设要改u到v的路径上的值。 我们先设tpu=top[u],tpv=top[v]。 1.如果tpu!=tpv，即不在一条重链上。我们就先改deep[tp]更深的那一条（lca原理）。 我们设deep[tpu]>deep[tpv]（小于就互换），然后在数据结构上修改id[tpu]~id[u]上的值。 2.如果tpu=tpv，即在同一条重链上后。 我们设deep[u] < deep[v]（大于就互换），修改id[u]~id[v]上的值，然后结束操作。
void change(int x,int y,int val) { int tx=top[x],ty=top[y]; while (tx!=ty) { if (deep[tx]<deep[ty]) { swap(tx,ty); swap(x,y); } changs(1,1,tot,id[tx],id[x],val); x=dad[tx]; tx=top[x]; } if (deep[x]>deep[y]) swap(x,y); if (x) changs(1,1,tot,id[x],id[y],val); }查询也一样。
似乎道理不多，不过有些难打。。。。
这道题我没有过，我也不知道哪里错了，上网弄了个大佬的标对拍，拍了几年没有拍出什么错。。。 这道题大意：一棵树，区间修改，单点查询。
#include<cstdio> #include<algorithm> #include<cmath> #include<cstdlib> #include<cstring> #pragma comment(linker, "/STACK:1024000000,1024000000"); #define fo(i,a,b) for(int i=a;i<=b;i++) #define ll long long using namespace std; const int maxn=5*1e4+5; int nnnn[maxn*2],fre[maxn],go[maxn*2],id[maxn],top[maxn],son[maxn],size[maxn],a[maxn]; int num,n,m,q,tot,now[maxn],dad[maxn],deep[maxn],ans; struct cy{ int val,lab; }tree[maxn*4]; void add(int x,int y) { go[++num]=y; nnnn[num]=fre[x]; fre[x]=num; } void dfs1(int x,int fa,int dep) { dad[x]=fa; size[x]=1; deep[x]=dep; int big=0; for(int i=fre[x];i;i=nnnn[i]){ if (go[i]==fa) continue; dfs1(go[i],x,dep+1); if (size[go[i]]>big) son[x]=go[i],big=size[go[i]]; size[x]+=size[go[i]]; } } void dfs2(int x,int tp) { id[x]=++tot; top[x]=tp; now[tot]=a[x]; if (son[x]!=-1) dfs2(son[x],tp); for(int i=fre[x];i;i=nnnn[i]){ if (go[i]==son[x]) continue; if (go[i]==dad[x]) continue; dfs2(go[i],go[i]); } } void maketree(int p,int l,int r)//线段树操作 { if (l==r) tree[p].val=now[l]; else { int mid=(l+r)>>1; maketree(p<<1,l,mid); maketree(p<<1|1,mid+1,r); } } void push(int x) { tree[x<<1].lab+=tree[x].lab; tree[x<<1|1].lab+=tree[x].lab; tree[x].lab=0; } void changs(int p,int l,int r,int a,int b,int val) { if (l==a&&r==b) { tree[p].lab+=val; return; } if(tree[p].lab) push(p); int mid=(l+r)>>1; if (b<=mid) changs(p<<1,l,mid,a,b,val); else if (a>mid) changs(p<<1|1,mid+1,r,a,b,val); else { changs(p<<1,l,mid,a,mid,val); changs(p<<1|1,mid+1,r,mid+1,b,val); } } void change(int x,int y,int val) { int tx=top[x],ty=top[y]; while (tx!=ty) { if (deep[tx]<deep[ty]) { swap(tx,ty); swap(x,y); } changs(1,1,tot,id[tx],id[x],val); x=dad[tx]; tx=top[x]; } if (deep[x]>deep[y]) swap(x,y); if (x) changs(1,1,tot,id[x],id[y],val); } void find(int p,int l,int r,int pos) { if (l==r) { tree[p].val=tree[p].val+tree[p].lab; tree[p].lab=0; ans=tree[p].val; } else { if(tree[p].lab) push(p); int mid=(l+r)>>1; if (pos<=mid) find(p<<1,l,mid,pos); else find(p<<1|1,mid+1,r,pos); } } int main() { freopen("T.in","r",stdin); freopen("T.out","w",stdout); scanf("%d%d%d",&n,&m,&q); fo(i,1,n) scanf("%d",&a[i]); fo(i,1,m){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } memset(son,255,sizeof(son)); dfs1(1,0,1); dfs2(1,1); maketree(1,1,tot); fo(i,1,q){ char ch; ch=getchar(); while (ch!='I'&&ch!='Q'&&ch!='D') ch=getchar(); if (ch=='I'){ int x,y,ac; scanf("%d%d%d",&x,&y,&ac); change(x,y,ac); } else if (ch=='D'){ int x,y,ac; scanf("%d%d%d",&x,&y,&ac); change(x,y,-ac); } else { int x; scanf("%d",&x); ans=0; find(1,1,tot,id[x]); printf("%d\n",ans); } } return 0; }谁要是发现错误可以告诉我，反正我很纳闷，估计是一些边界的错误。
