适用范围
总之就是数据结构的基础问题。
总的来说，树链剖分可以在\(O(m\log n)\)的时间复杂度中，解决大多数树上路径问题，包括其修改、维护和查询。
例如这样的一道模板题
又例如……（请直接跳到本文最后一章）
产品简介
树链剖分有两种：重链剖分，长链剖分。（按照剖分树的方式区分）
重链剖分中有如下一些定义：
重儿子：除叶子节点外，每个点的儿子中，子树最大（即子树节点最多）的子节点。（每个节点只有一个）
轻儿子：除叶子节点外，每个点的儿子中，不是重儿子的节点。（每个节点可能有不止一个）
重边：除叶子节点外，两端点都是重儿子的边。它用于构成重链。
轻边：除叶子节点外，每个节点到其轻儿子的边。它起到连接重链的作用。
重链：一些重边连成的链。
轻链：一些轻边连成的链。
而长链剖分，相当于将重链剖分中“子树大小”的部分替换为了“子树深度”，例如：
长儿子：除叶子节点外，每个点的儿子中，子树最深（即子树的层数最大）
综上，树链剖分是对树进行剖分，最终使其变成一些线性且不相交的链的算法。这时候，对树的操作，就变成了在链上的操作。
链可是经常作为部分分存在的好东西啊
生效原理
关于它的性质和实现方式。
树链剖分的性质
每个节点只能属于一条链，如果每次都选择节点更多的分支建链，建出的链自然会更长，从而，链的数量也就会更少。
由此，对于重链剖分，有这样的性质：
从根节点到任意一个叶子只需要经过\(O(\log_{2}n)\)条重链。
（因为每条轻边意味着树的大小至少缩小了一半。所以整棵树中，轻边的数量是\(O(\log_{2}n)\)的。而两条重链必然由轻边连接。）
它的另一个性质是：每条重链的DFS序是连续且有序的。
这一性质使重链得以被线段树维护。对于树上区间的修改查询问题，它“继承”了线段树的优势。
树链剖分的实现
详见代码解析（指路）
使用范例
DFS序与线段树
我们知道两个性质：
- 每条重链内的DFS编号连续且有序
- 每棵子树内的DFS编号连续且有序
所以以DFS编号建立线段树。则同一条重链的节点，在线段树上是一个连续区间。
路径上的修改与查询
假设给出节点\(x\)，\(y\)，要修改/查询\(x\)到\(y\)最短路径上节点的权值。
这其实类似于求LCA的过程。（毕竟树上最短路径嘛）而这个过程又类似于ST表求LCA的过程。
不妨假设\(x\)链头深度更深，设\(dfn[u]\)表示节点\(u\)的dfs编号。
修改
首先，令\(x\)沿重链向上跳到链头。修改这段路径中的节点权值。（对应线段树中区间为\([dfn[x], dfn[链头]\)）
然后将\(x\)跳到上方的重链，并再次执行上一操作。重复这两步，直到\(x\)与\(y\)的链头深度相同。
然后将\(x\)和\(y\)同时向上跳（类似上两步的方法），直到它们处于同一条重链之中。此时再修改\(x\)和\(y\)之间的节点即可。（对应线段树中区间为\([dfn[x], dfn[y]]\)）
过程中的每次修改，直接调用update函数即可。
查询
路径查询和路径修改一模一样。只需要把update函数换成query函数。
（甚至可以用同一个求LCA函数实现查询&修改）
子树里的修改与查询
子树里的操作相比于路径更加简单。
一棵子树中节点的DFS序是连续且有序的，所以可以直接用线段树进行操作（当然，提前处理子树的\(l\)和\(r\)）