之前勉强讲完了一个题，但还是理解的不太好

睡一觉起来看了百度百科后豁然贯通   

树链剖分和线段树的区别就是它可以维护一条链，，比单纯的线段树要机智一些（2333）。

所以说科普一下百度百科还是很有必要的

方法

 

 

常见的 剖分的方法是轻重树链剖分（启发式剖分）

将树中的边分为：轻边和重边 ž定义size(X)为以X为根的子树的节点个数。 ž令V为U的儿子节点中size值最大的节点，那么边(U,V)被称为重边，树中重边之外的边被称为轻边。

性质：ž轻边(U,V)，size(V)<=size(U)/2。 ž从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。

具体步骤

预处理

第一遍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)

top[

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])

top[

x]→

x

if dep[

x]>dep[

y]

then SWAP (

x,y)

QUERY-IT(tid[

x],tid[

y])

//QUERY-IT(

l,r)为数据结构的查询操作，

题目不同，选用不同的数据结构来维护值，通常有线段树和splay（发现我还不回spaly,,,,,没事的）