树链剖分/重链剖分

什么是树链剖分/重链剖分

我们可以弄一道例题来看看：
现在给定一棵 \(n（1 \le n \le 10^5）\) 节点的树，每个节点上有一个数值，现在你可以进行 $m ( 1 \le m \le 10^5) $ 次操作。格式如下：

• 1 x z 表示将 \(x\) 到 \(y\) 最短路径上的节点值加上 \(z\) 。
  
• 2 x y 表示树求 \(x\) 到 \(y\) 最短路径上的权值和。
  
• 3 x y 将子树 \(x\) 下的每个节点的权值加上 \(y\) 。
  
• 4 x 求子树 \(x\) 下每个节点的权值之和。
  怎么写呢？当然，你需要前置知识线段树。接下来，且听我慢慢道来。
  

先从构造一个美满的剖分数组开始

我们知道，一棵树可以通过DFS构造成一个序列，其中对于恣意一棵子树（包括根节点），我们把他的节点个数叫做 \(siz\) 。子树 \(x\) 的大小就是 \(siz_x\) 。那这对剖分有什么资助呢？对于一棵树的DFS序举例如下：

1.     1
2.    / \
3.   2   3
4. /
5. 4
6. \
7.   5

复制代码

那么DFS后，序列如下：

1. 1 2 4 5 3

复制代码

可以看到，子树 \(x\) 到 \(x+siz_x\) ，就是整个子树 \(x\) 。我们临时叫这个数组为剖分数组 \(tag\)。但这样并不是最优的，有的的时间无法保证前面阐述的规律，这个时间怎么办呢？我们可以分析一下，在这棵树中，\(1\) 有两个孩子，分别是 \(2\) 和 \(3\) ，而且 \(2\) 的子树大小比 \(3\) 大，那么我们就规定 \(2\) 是 \(1\) 的 重孩子 。从 \(1\) 到 \(2\) 的这条边我们叫做重链。可以得知，对于恣意一个非叶子节点，都有其独有的重孩子，我们就可以根据重孩子来构造DFS的先后，因为我们优先遍历一棵树的所有重孩子，以是所有重孩子一定是连在一起的，上面就是一个说明。那优先从重孩子开始还有什么好处呢？我们知道，如果从轻孩子开始遍历去构造这个数组，那么时间复杂度可能会达到 \(O(n)\)（见后文）。但是如果从重孩子开始的话，就不一样了，我们可以证明其时间复杂度可以来到 \(O(\log^2n)\) 的单次询问复杂度，证明如下：
对于节点 \(u\) ，其重孩子 \(v\) 必然是所有子节点中子树最大的那个，即为:

\[size(v) \ge size(w) \forall w \in children(u)\]
又因为重孩子的子树大小 \(\ge\) 其他所有子节点的子树大小，因此对于恣意轻孩子 \(w\) 有：

\[size(w)\le size(v)\]
又又因为所有节点子树个数+1等于其父亲节点的包含的节点个数（有点拗口），即为：

\[size(v)+\sum_{轻孩子w} size(w)+1 = size(u)\]
根据上面的第二,三条定理，解不等式方程，可以得到对于：

\[\sum_{轻孩子w}size(w) \le size(u)-size(v)-1\]
以是可以知道：**如果某个轻孩子节点\(w\) 的子树大小大于 \(\frac{1}{2} size(u)\), 则以上定理不建立，违背重孩子的界说，以是，必然有对于恣意 \(w\)：

\[size(w)\le \frac{size(u)}{2}\]
因此，从根节点到恣意节点得到路径上，最多只有 \(O(\log n)\) 条轻边（因为每次碰到轻边子树大小随见到原来的 \frac{1}{2},以是至多 \(\log^2n\) 就会到达根节点）
而又因为重孩子是连续的一段区间，以是一次线段树修改就可以，再加上轻边修改是每次 \(O(\log n)\)，最多 \(\log n\) 条，以是是 \(O(\log n)\) 时间复杂度，证毕。
至此，我们的树链剖分的关键部分就已经完成。
Code如下：

1. void dfs1(int root, int fa) {
2.     fath[root] = fa;
3.     siz[root] = 1;
4.     dep[root] = dep[fa] + 1;
5.     for(auto i : tree[root]) {
6.         if(i == fa) continue;
7.         dfs1(i, root);
8.         siz[root] += siz[i];
9.         if(siz[i] > siz[son[root]])
10.             son[root] = i;
11.     }
12. }
14. void dfs2(int root, int tp) {
15.     top[root] = tp;
16.     dfn[root] = ++cnt;
17.     rev[cnt] = root;
18.     if(!son[root]) return;
19.     dfs2(son[root], tp);
20.     for(auto i : tree[root]) {
21.         if(i == fath[root] || i == son[root]) continue;
22.         dfs2(i, i);
23.     }
24. }

复制代码

其中 siz 是表示大小，top表示链头（见后文），dfn 表示对于 \(root\) 节点，在剖分数组里的位置。rev 是反的 dfn，cnt 全局计数器，son 记录重孩子编号，dep 表示深度。
利用链表的思想，完成perfect的查询/修改

我们已经知道，怎么分割一个有效的剖分数组。就是不会用，怎么办呢？
照旧拿出一棵树：

1.     1
2.    / \
3.   2   5
4. / \   \
5. 3   7   6
6. \      /
7.   4    8
8. / \
9. 9  10

复制代码

构造出来的序列如下(-表示重链，  表示轻边）

1. 1-2-3-4-9 10 7 5-6-8

复制代码

现在我们将 \(10\) 到 \(8\) 之间的，过程如下：

• 先使所有重链的链头为深度最小的节点，好比 \(8,6,5\) 的链头都是 \(5\)，\(9,4,3,2,1\) 的链头都是 \(1\)
  
• 令所有轻边的链头就是其自己
  那么修改的时间，每次选择深度大的条跳跃，直到两者链头雷同。那么此时只需要修改当前 \(\min{u,v}\) 到 \(\max{u,v}\) （询问/操作的两个端点）就可以了！。
  到这里我们也可以知道了吧，按照轻边来的话时间复杂度是 \(O(n)\) 的哦。千万警惕！
  因为查询和修改代码类似，就不详细撰述了。
  

Code For Luogu P3384

[code]#include#define int long longusing namespace std;const int maxn = 1e5+100;int num[maxn],fath[maxn],top[maxn],son[maxn],dep[maxn],siz[maxn];int lay[maxnz;            udp(x,y,z);        }        else if(op==2){            cin>>x>>y;            coutz;            update(1,1,n,tag1[x],tag1[x]+siz[x]-1,z);        }        else if(op==4){            cin>>x;            cout