[0.x]前言

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。
──OI Wiki

[1.x] 轻重链剖分

[1.1.x]前置概念

  • 重儿子：对于一个节点，它的儿子中最大的一个儿子为重儿子（子树最大的儿子）
  • 轻儿子：除了重儿子的其他儿子
  • 重边：连接重儿子的边
  • 轻边：除了重边的边
  • 重链：把1个轻儿子和相邻重儿子连起来的链，即一个重链总是以轻儿子或者根重儿子为头的重儿子串

[1.2.x]预处理

我们进行两次dfs，分别维护这些东西

[1.2.1.x]第一次dfs

第一次dfs主要是确定重儿子，为第二次dfs做准备，顺便处理可以一次性处理的东西。

  • dep[i]节点i的深度
  • fa[i]节点i的父亲
  • son[i]节点i的重儿子
  • size[i]节点i为根的子树大小
  1. inline void dfs1(int now,int father){
  2.     size[now] = 1 , deep[now] = deep[father] + 1 , fa[now] = father;
  3.     for(int i = head[now];i;i = next[i]){
  4.         if(ver[i] == fa[now]) continue;
  5.         dfs1(ver[i],now);
  6.         size[now] += size[ ver[i] ];
  7.         son[now] = size[ son[now] ] > size[ ver[i] ] ? son[now] : ver[i]; // 更新重儿子
  8.     }
  9.     return;
  10. }

[1.2.2.x]第二次dfs

第二次dfs是在根据已经得到的重儿子来确定一个特别的dfs序，来维护一些性质

这个dfs序号的特别要求是：先走重儿子，这样能保证重儿子链的dfs序是连续的

  • top[i]节点i所在的重链头
  • id[i]节点i的dfs序号
  • b[id[i]]通过节点i的dfs序索引a[i]
  1. inline void dfs2(int now,int toper){
  2.     id[now] = ++id[0] , top[now] = toper , b[id[0]] = a[now];
  3.     if(!son[now]) return; // 没有重儿子即叶子节点
  4.     dfs2(son[now],toper); // 重儿子先走
  5.     for(int i = head[now];i;i = next[i]){
  6.         if(id[ ver[i] ]) continue;
  7.         dfs2(ver[i],ver[i]);
  8.     }
  9.     return;
  10. }

[1.3.x]线段树维护

经过预处理后，我们可以发现，所有在同一个重链中的重儿子的dfs序是连续的，同时，还有一个性质，以i为根的子树上所有的点的dfs序都在[id[i],id[i]+size[i]-1]中。因此我们可以以dfs序为索引建立线段树

  1. int TOT;
  2. struct node{
  3.     int l,r;
  4.     ll sum,tag;
  5.     int dis(){return r-l+1;}
  6.     node * ls, * rs;
  7. }Tree[4*N];
  9. inline node * create(){return &Tree[++TOT];}
  11. inline void pushdown(node * cur){
  12.     cur->ls->sum += cur->tag * cur->ls->dis(), cur->ls->sum %= p;
  13.     cur->ls->tag += cur->tag , cur->ls->tag %= p;
  14.     cur->rs->sum += cur->tag * cur->rs->dis(), cur->rs->sum %= p;
  15.     cur->rs->tag += cur->tag , cur->rs->tag %= p;
  16.     cur->tag = 0;
  17.     return;
  18. }
  20. inline void pushup(node * cur){cur->sum = (cur->ls->sum + cur->rs->sum)%p;}
  22. inline void build(node * cur,int l,int r){
  23.     cur->l = l , cur->r = r , cur->sum = cur->tag = 0;
  24.     if(cur->l == cur->r){cur->sum = b[l];return;}
  25.     int mid = (l+r)>>1;
  26.     cur->ls = create() , cur->rs = create();
  27.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  28.     pushup(cur);
  29.     return;
  30. }
  32. inline void edit(node * cur,int l,int r,int x){
  33.     if(l > cur->r || r < cur->l) return;
  34.     if(l <= cur->l && cur->r <= r){
  35.         cur->sum += x * cur->dis() % p , cur->sum %= p , cur->tag += x;
  36.         return;
  37.     }
  38.     if(cur->l == cur->r) return;
  39.     pushdown(cur);
  40.     if(l <= cur->ls->r) edit(cur->ls,l,r,x);
  41.     if(r >= cur->rs->l) edit(cur->rs,l,r,x);
  42.     pushup(cur);
  43.     return;
  44. }
  46. inline ll query(node * cur,int l,int r){
  47.     if(l > cur->r || r < cur->l) return 0;
  48.     if(l <= cur->l && cur->r <= r) return cur->sum;
  49.     pushdown(cur);
  50.     return (query(cur->ls,l,r) + query(cur->rs,l,r))%p;
  51. }

[1.4.x]实现

[1.4.1.x]链上修改

首先这里肯定要用到线段树的区间修改，怎样增加效率呢。首先我们已经有了所有重链的序号连续，那自然通过top[i]不断向上跳，类似于树上倍增LCA，不断上跳直到两个点在同一个重链中。

  1. inline void edit_chain(node * cur){
  2.     //把x到y都加上z
  3.     while(top[x] != top[y]){
  4.         if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  5.         edit(cur,id[top[x]],id[x],z);
  6.         x = fa[ top[x] ];
  7.     }
  8.     if(id[x] > id[y]) std::swap(x,y);
  9.     edit(cur,id[x],id[y],z);
  10.     return;
  11. }

链上查询和链上修改同理。

  1. inline void query_chain(node * cur){
  2.     //查询x到y的和
  3.     ll ans = 0;
  4.     while(top[x] != top[y]){
  5.         if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  6.         ans += query(cur,id[top[x]],id[x]) , ans %= p;
  7.         x = fa[top[x]];
  8.     }
  9.     if(id[x] > id[y]) std::swap(x,y);
  10.     ans += query(cur,id[x],id[y]) , ans %= p;
  11.     cout << ans << "\n";
  12.     return;
  13. }

树上修改和查询就更简单了，直接操作[id[i],id[i]+size[i]-1]就行

  1. inline void edit_tree(node * cur){
  2.     //给x的子树都加上z
  3.     edit(cur,id[x],id[x]+size[x]-1,z);
  4.     return;
  5. }
  7. inline void query_tree(node * cur){
  8.     //查询x的子树和
  9.     cout << query(cur,id[x],id[x]+size[x]-1) << "\n";
  10.     return;
  11. }

区间最值的维护和区间和的维护基本上类似，可以参考相关题目第二题的代码。

[1.5.x]相关题目

P3384 【模板】轻重链剖分

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i)  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. using std::string;using std::cin;using std::cout;
  18. const int N = 1e5+5;
  19. int n,m,root,p,a[2*N],b[2*N],x,y,z,opt;
  20. int head[2*N],next[2*N],ver[2*N],tot;
  21. int fa[2*N],top[2*N],deep[2*N],son[2*N],size[2*N],id[2*N];
  23. //------------------------------------------------------
  25. inline void link(int x,int y){ver[++tot] = y , next[tot] = head[x] , head[x] = tot;}
  27. inline void dfs1(int now,int father){
  28.     size[now] = 1 , deep[now] = deep[father] + 1 , fa[now] = father;
  29.     for(int i = head[now];i;i = next[i]){
  30.         if(ver[i] == fa[now]) continue;
  31.         dfs1(ver[i],now);
  32.         size[now] += size[ ver[i] ];
  33.         son[now] = size[ son[now] ] > size[ ver[i] ] ? son[now] : ver[i]; // 更新重儿子
  34.     }
  35.     return;
  36. }
  38. inline void dfs2(int now,int toper){
  39.     id[now] = ++id[0] , top[now] = toper , b[id[0]] = a[now];
  40.     if(!son[now]) return; // 没有重儿子即叶子节点
  41.     dfs2(son[now],toper); // 重儿子先走
  42.     for(int i = head[now];i;i = next[i]){
  43.         if(id[ ver[i] ]) continue;
  44.         dfs2(ver[i],ver[i]);
  45.     }
  46.     return;
  47. }
  49. //------------------------------------------------------
  51. int TOT;
  52. struct node{
  53.     int l,r;
  54.     ll sum,tag;
  55.     int dis(){return r-l+1;}
  56.     node * ls, * rs;
  57. }Tree[4*N];
  59. inline node * create(){return &Tree[++TOT];}
  61. inline void pushdown(node * cur){
  62.     cur->ls->sum += cur->tag * cur->ls->dis(), cur->ls->sum %= p;
  63.     cur->ls->tag += cur->tag , cur->ls->tag %= p;
  64.     cur->rs->sum += cur->tag * cur->rs->dis(), cur->rs->sum %= p;
  65.     cur->rs->tag += cur->tag , cur->rs->tag %= p;
  66.     cur->tag = 0;
  67.     return;
  68. }
  70. inline void pushup(node * cur){cur->sum = (cur->ls->sum + cur->rs->sum)%p;}
  72. inline void build(node * cur,int l,int r){
  73.     cur->l = l , cur->r = r , cur->sum = cur->tag = 0;
  74.     if(cur->l == cur->r){cur->sum = b[l];return;}
  75.     int mid = (l+r)>>1;
  76.     cur->ls = create() , cur->rs = create();
  77.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  78.     pushup(cur);
  79.     return;
  80. }
  82. inline void edit(node * cur,int l,int r,int x){
  83.     if(l > cur->r || r < cur->l) return;
  84.     if(l <= cur->l && cur->r <= r){
  85.         cur->sum += x * cur->dis() % p , cur->sum %= p , cur->tag += x;
  86.         return;
  87.     }
  88.     if(cur->l == cur->r) return;
  89.     pushdown(cur);
  90.     if(l <= cur->ls->r) edit(cur->ls,l,r,x);
  91.     if(r >= cur->rs->l) edit(cur->rs,l,r,x);
  92.     pushup(cur);
  93.     return;
  94. }
  96. inline ll query(node * cur,int l,int r){
  97.     if(l > cur->r || r < cur->l) return 0;
  98.     if(l <= cur->l && cur->r <= r) return cur->sum;
  99.     pushdown(cur);
  100.     return (query(cur->ls,l,r) + query(cur->rs,l,r))%p;
  101. }
  103. //------------------------------------------------------
  105. inline void edit_chain(node * cur){
  106.     //把x到y都加上z
  107.     while(top[x] != top[y]){
  108.         if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  109.         edit(cur,id[top[x]],id[x],z);
  110.         x = fa[ top[x] ];
  111.     }
  112.     if(id[x] > id[y]) std::swap(x,y);
  113.     edit(cur,id[x],id[y],z);
  114.     return;
  115. }
  117. inline void query_chain(node * cur){
  118.     //查询x到y的和
  119.     ll ans = 0;
  120.     while(top[x] != top[y]){
  121.         if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  122.         ans += query(cur,id[top[x]],id[x]) , ans %= p;
  123.         x = fa[top[x]];
  124.     }
  125.     if(id[x] > id[y]) std::swap(x,y);
  126.     ans += query(cur,id[x],id[y]) , ans %= p;
  127.     cout << ans << "\n";
  128.     return;
  129. }
  131. inline void edit_tree(node * cur){
  132.     //给x的子树都加上z
  133.     edit(cur,id[x],id[x]+size[x]-1,z);
  134.     return;
  135. }
  137. inline void query_tree(node * cur){
  138.     //查询x的子树和
  139.     cout << query(cur,id[x],id[x]+size[x]-1) << "\n";
  140.     return;
  141. }
  143. //------------------------------------------------------
  145. int main(){
  146.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  147.     //freopen("in.in", "r", stdin);
  148.     cin >> n >> m >> root >> p;
  149.     rep(i,1,n) cin >> a[i];
  150.     rep(i,1,n-1){
  151.         cin >> x >> y;
  152.         link(x,y) , link(y,x);
  153.     }
  154.     fa[root] = 0 , deep[fa[root]] = 0;
  155.     dfs1(root,0);
  156.     dfs2(root,root);
  157.     node * Root = create();
  158.     build(Root,1,n);
  159.     while(m--){
  160.         cin >> opt;
  161.         if(opt == 1){//链改
  162.             cin >> x >> y >> z;
  163.             z %= p;
  164.             edit_chain(Root);
  165.         } else if(opt == 2){//链查
  166.             cin >> x >> y;
  167.             query_chain(Root);
  168.         } else if(opt == 3){//树改
  169.             cin >> x >> z;
  170.             z %= p;
  171.             edit_tree(Root);
  172.         } else if(opt == 4){//树查
  173.             cin >> x;
  174.             query_tree(Root);
  175.         }
  176.     }
  177.     return 0;
  178. }

P2590 [ZJOI2008]树的统计

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i) 
  14. #define mkp std::make_pair
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. using std::string;using std::cin;using std::cout;
  18. inline bool cmp(int x,int y){return x < y;}
  19. const int inf = 1e9+9;
  20. const int N = 1e6+9;
  21. const double eps = 1e-7;
  22. int _,n,m,a[2*N],u,v;
  23. string str;
  25. //----------------------------
  27. int head[2*N],next[2*N],ver[2*N],tot;
  28. inline void link(int x,int y){ver[++tot] = y , next[tot] = head[x] , head[x] = tot;}
  30. //----------------------------
  32. int fa[2*N],top[2*N],son[2*N],size[2*N],deep[2*N],id[2*N],b[2*N];
  34. inline void dfs1(int now,int fathter){
  35.     fa[now] = fathter , deep[now] = deep[fathter] + 1 , size[now] = 1;
  36.     for(int i = head[now];i;i = next[i]){
  37.         if(ver[i] == fathter) continue;
  38.         dfs1(ver[i],now);
  39.         size[now] += size[ ver[i] ];
  40.         son[now] = size[ son[now] ] > size[ son[ver[i]] ] ? son[now] : ver[i];
  41.     }
  42.     return;
  43. }
  45. inline void dfs2(int now,int toper){
  46.     id[now] = ++id[0] , b[ id[0] ] = a[now] , top[now] = toper;
  47.     if(!son[now]) return;
  48.     dfs2(son[now],toper);
  49.     for(int i = head[now];i;i = next[i]){
  50.         if(id[ ver[i] ]) continue;
  51.         dfs2(ver[i],ver[i]);
  52.     }
  53.     return;
  54. }
  56. //----------------------------
  58. int TOT;
  59. struct node{
  60.     int l,r,sum,max;
  61.     node * ls , * rs;
  62. }Tree[4*N];
  64. inline node * create(){return &Tree[++TOT];}
  66. inline void pushup(node * cur){cur->sum = cur->ls->sum + cur->rs->sum , cur->max = std::max(cur->ls->max,cur->rs->max);}
  68. inline void build(node * cur,int l,int r){
  69.     cur->l = l , cur->r = r , cur->sum = cur->max = 0;
  70.     if(l == r){
  71.         cur->sum = cur->max = b[l];
  72.         return;
  73.     }
  74.     int mid = (l+r) >> 1;
  75.     cur->ls = create() , cur->rs = create();
  76.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  77.     pushup(cur);
  78.     return;
  79. }
  81. inline void edit(node * cur){
  82.     if(cur->l == cur->r){
  83.         cur->sum = cur->max = v;
  84.         return;
  85.     }
  86.     if(u <= cur->ls->r) edit(cur->ls);
  87.     if(cur->rs->l <= u) edit(cur->rs);
  88.     pushup(cur);
  89.     return;
  90. }
  92. inline int query_max(node * cur){
  93.     if(cur->r < u || v < cur->l) return -inf;
  94.     if(u <= cur->l && cur->r <= v) return cur->max;
  95.     return std::max(query_max(cur->ls),query_max(cur->rs));
  96. }
  98. inline int query_sum(node * cur){
  99.     if(cur->r < u || v < cur->l) return 0;
  100.     if(u <= cur->l && cur->r <= v) return cur->sum;
  101.     return query_sum(cur->ls) + query_sum(cur->rs);
  102. }
  104. //----------------------------
  106. int main(){
  107.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  108.     //freopen("in.in", "r", stdin);
  109.     cin >> n;
  110.     rep(i,1,n-1){
  111.         cin >> u >> v;
  112.         link(u,v) , link(v,u);
  113.     }
  114.     rep(i,1,n) cin >> a[i];
  116.     //----------------------------
  118.     dfs1(1,1) , dfs2(1,1);
  119.     node * root = create();
  120.     build(root,1,n);
  122.     //----------------------------
  124.     cin >> m;
  125.     while(m--){
  126.         cin >> str >> u >> v;
  127.         if(str == "CHANGE"){
  128.             u = id[u];
  129.             edit(root);
  130.         } else if(str == "QMAX"){
  131.             int x = u , y = v , ans = -inf;
  132.             while(top[x] != top[y]){
  133.                 if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  134.                 u = id[ top[x] ] , v = id[x] , x = fa[ top[x] ] , ans = std::max(ans,query_max(root));
  135.             }
  136.             if(id[x] > id[y]) std::swap(x,y);
  137.             u = id[x] , v = id[y] , ans = std::max(ans,query_max(root));
  138.             cout << ans << "\n";
  139.         } else if(str == "QSUM"){
  140.             int x = u , y = v , ans = 0;
  141.             while(top[x] != top[y]){
  142.                 if(deep[ top[x] ] < deep[ top[y] ]) std::swap(x,y);
  143.                 u = id[ top[x] ] , v = id[x] , x = fa[ top[x] ] , ans += query_sum(root);
  144.             }
  145.             if(id[x] > id[y]) std::swap(x,y);
  146.             u = id[x] , v = id[y] , ans += query_sum(root);
  147.             cout << ans << "\n";
  148.         }
  149.     }
  150.     return 0;
  151. }

P3178 [HAOI2015]树上操作

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i) 
  14. #define mkp std::make_pair
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. using std::string;using std::cin;using std::cout;
  18. inline bool cmp(int x,int y){return x < y;}
  20. const int N = 1e5+9;
  21. const int inf = 1e9+9;
  22. const double eps = 1e-7;
  23. int _,n,m,a[2*N],opt,u,v,w;
  24. //----------------------------
  25. int head[2*N],ver[2*N],next[2*N],tot;
  26. inline void link(int x,int y){ver[++tot] = y , next[tot] = head[x] , head[x] = tot;}
  27. //----------------------------
  28. int fa[2*N],top[2*N],deep[2*N],size[2*N],son[2*N],id[2*N],b[2*N];
  30. inline void dfs1(int now,int father){
  31.     fa[now] = father , deep[now] = deep[father] + 1 , size[now] = 1;
  32.     for(int i = head[now];i;i = next[i]){
  33.         if(ver[i] == father) continue;
  34.         dfs1(ver[i],now);
  35.         size[now] += size[ ver[i] ];
  36.         son[now] = size[ son[now] ] > size[ ver[i] ] ? son[now] : ver[i];
  37.     }
  38. }
  40. inline void dfs2(int now,int toper){
  41.     top[now] = toper , id[now] = ++id[0] , b[ id[0] ] = a[now];
  42.     if(!son[now]) return;
  43.     dfs2(son[now],toper);
  44.     for(int i = head[now];i;i = next[i]){
  45.         if(id[ ver[i] ]) continue;
  46.         dfs2(ver[i],ver[i]);
  47.     }
  48. }
  49. //----------------------------
  50. int TOT;
  51. struct node{
  52.     int l,r;
  53.     ll tag,sum;
  54.     node * ls , * rs;
  55.     ll dis(){return r-l+1;}
  56. }Tree[4*N];
  58. inline node * create(){return &Tree[++TOT];}
  60. inline void pushup(node * cur){cur->sum = cur->ls->sum + cur->rs->sum;}
  62. inline void pushdown(node * cur){
  63.     cur->ls->tag += cur->tag , cur->rs->tag += cur->tag;
  64.     cur->ls->sum += cur->tag * cur->ls->dis();
  65.     cur->rs->sum += cur->tag * cur->rs->dis();
  66.     cur->tag = 0;
  67.     return;
  68. }
  70. inline void build(node * cur,int l,int r){
  71.     cur->l = l , cur->r = r , cur->tag = 0;
  72.     if(l == r){cur->sum = b[l];return;}
  73.     int mid = (l+r) >> 1;
  74.     cur->ls = create() , cur->rs = create();
  75.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  76.     pushup(cur);
  77. }
  79. inline void edit(node * cur){
  80.     if(v < cur->l || cur->r < u) return;
  81.     if(u <= cur->l && cur->r <= v){
  82.         cur->tag += w , cur->sum += w * cur->dis();
  83.         return;
  84.     }
  85.     if(cur->l == cur->r) return;
  86.     pushdown(cur);
  87.     if(u <= cur->ls->r) edit(cur->ls);
  88.     if(cur->rs->l <= v) edit(cur->rs);
  89.     pushup(cur);
  90. }
  92. inline ll query(node * cur){
  93.     if(v < cur->l || cur->r < u) return 0;
  94.     if(u <= cur->l && cur->r <= v) return cur->sum;
  95.     pushdown(cur);
  96.     return query(cur->ls) + query(cur->rs);
  97. }
  99. //----------------------------
  100. int main(){
  101.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  102.     cin >> n >> m;
  103.     rep(i,1,n) cin >> a[i];
  104.     rep(i,1,n-1){
  105.         cin >> u >> v;
  106.         link(u,v) , link(v,u);
  107.     }
  108.     dfs1(1,1) , dfs2(1,1);
  109.     node * root = create();
  110.     build(root,1,n);
  111.     int p,x;
  112.     while(m--){
  113.         cin >> opt;
  114.         if(opt == 1){//point edit
  115.             cin >> p >> x;
  116.             u = v = id[p] , w = x;
  117.             edit(root);
  118.         } else if(opt == 2){//tree edit
  119.             cin >> p >> x;
  120.             u = id[p] , v = id[p] + size[p] - 1 , w = x;
  121.             edit(root);
  122.         } else {//query
  123.             cin >> p;
  124.             ll ans = 0;
  125.             while(top[1] != top[p]){
  126.                 u = id[ top[p] ] , v = id[p];
  127.                 ans += query(root);
  128.                 p = fa[ top[p] ];
  129.             }
  130.             u = id[1] , v = id[p];
  131.             cout << ans + query(root) << "\n";
  132.         }
  133.     }
  134.     return 0;
  135. }