一般适用于对于树的区间查询与修改。
几个定义：
树链：树上两点之间的路径。
剖分：将树上的边划分为轻边和重边。
重儿子：在 u 的儿子节点中，siz最大的那个节点即为 u 的重儿子。（若存在多个，则任选一个）
轻儿子：除重儿子之外的所有儿子节点均为轻儿子。
重边：父节点与重儿子之间的连边。
轻边：父节点与轻儿子之间的连边。
重链：由重边首尾相连组成的路径。
操作之前需要通过dfs初始化一些信息，fa[] , son[] , siz[] , top[] , dot_site[] , dep[] ，seg[]。
fa[s] ：s 的父节点。根节点无意义。
son[s] ：s的重儿子。叶子节点无意义。
dep[s] ：s的深度。
top[s] ：s所在链的深度最小的点。
siz[s] ：以s为根节点的子树上的节点总数。
dot_site[s] , s 在dfs时的时间戳。
seg为dfs时的次序。
如图所示：
途中粗线即为重边，细线即为轻边。
则图中重链有 ：1. （1 -> 4 -> 7 -> 10） 2. (2 -> 12) 3. ( 6->9 ) 。
图中点旁边的数字即为相应的点的 top[] 。
为了保证重链上的点在 dfs 时连续，则在dfs时要优先对其重儿子进行dfs(显然除叶子节点外的所有节点均存在重儿子)。
则dfs完成后 seg存储的内容为 { 1,4,7,10,11,6,9,5,2,12 , 3}。
然后对 seg 建立线段树，继而对线段树进行查询和更新。
因为任意两点间的重链和轻边的数量均不超过 log(n)，n 两点之间的边的条数，所以在对任意一段路径查询和更新时，其对线段
树的操作次数不会超过2*log（n）。(所示树链剖分的一个性质吧)。
以查询为例。
while(1)
{
设 fu = top[u] , fv = top[v]。
1. 当fu != fv(设 dep[fu] > dep[fv] ) 时，查询seg[] 的子区间 [ dot_site[fu] , dot_site[u] ]上的最值 ， u = fa[fu] .
2. 当 fu == fv 时，u，v在一条重链上，若 u == v,查询结束，否则查询 [dot_site[ u ] ,dot_site[ v ] ] (设dep[u] < dep[v])，查询结束。
}
心情有点小低谷。。。墨迹了好久才写完。。。离别的前奏总是这样伤感。
原文：http://blog.csdn.net/zmx354/article/details/22213569
