树链剖分模板

预处理 第一遍dfs求出树每个结点的深度deep[x]，其为根的子树大小size[x] 以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先 第二遍dfs ž根节点为起点，向下拓展构建重链 选择最大的一个子树的根继承当前重链 其余节点，都以该节点为起点向下重新拉一条重链 ž给每个结点分配一个位置编号，每条重链就相当于一段区间，用数据结构去维护。 把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可 修改操作 ž1、单独修改一个点的权值 根据其编号直接在数据结构中修改就行了。 2、修改点u和点v的路径上的权值 （1）若u和v在同一条重链上 直接用数据结构修改pos[u]至pos[v]间的值。 （2）若u和v不在同一条重链上 一边进行修改，一边将u和v往同一条重链上靠，然后就变成了情况（1）。 伪代码 CHANGE (x, y ,d) while top[x]≠top[y] do if dep[top[x]]<dep[top[y]] then SWAP(x,y), SWAP (gx,gy) CHANGE-IT(tid[top[x]],tid[x],d) fa[x]→x if dep[x]>dep[y] then SWAP (x,y) CHANGE-IT(tid[x],tid[y],d) //CHANGE-IT(l,r,d)为数据结构的修改操作：将区间[l,r]上的所有权值改为d 查询操作 ž查询操作的分析过程同修改操作 伪代码 QUERY (x, y) while top[x]≠top[y] do if dep[top[x]]<dep[top[y]] then SWAP (x,y), SWAP (gx,gy) QUERY-IT(tid[top[x]],tid[x]) fa[x]→x if dep[x]>dep[y] then SWAP (x,y) QUERY-IT(tid[x],tid[y]) //QUERY-IT(l,r)为数据结构的查询操作， 题目不同，选用不同的数据结构来维护值，通常有线段树和splay [2]