当 BIT 遇到 DFS 序

roger_yrj · 2024-11-17 19:50:23 · 算法·理论

众所周知，当一棵树求出 DFS 序后，可以将子树拍成区间。这时，BIT 就能处理很多树上问题。

单点加，子树求和
- 其实就是单点加，区间求和。
单点加，链求和
- 维护每个点到根的和，那么单点加相当于子树加。
- 链求和拆成到根的链（下同），那么链求和相当于单点查。
子树加，单点查
- 其实就是区间加，单点查。差分即可。
链加，单点查
- 做树上差分后，问题转化为单点加，子树求和
子树加，子树求和
- 相当于区间加区间求和。这是一个 BIT 经典问题。
- 还是做差分，设原数组为 a，差分数组为 d，前缀和数组为 sum。
- d_i=a_i-a_{i-1}$，$a_i=\sum\limits_{j=1}^id_j
- sum_i=\sum\limits_{k=1}^ia_k=\sum\limits_{k=1}^i\sum\limits_{j=1}^kd_j=\sum\limits_{k=1}^id_k\times(n-k+1)=(n+1)\sum\limits_{k=1}^id_k-\sum\limits_{k=1}^ik\times d_k
- 我们可以维护 d_i 和 i\times d_i，进而维护前缀和。
链加，子树求和
- 维护每个点的子树和，链加拆成到根的链。
- 对于一次链加，只有链上的点会受影响。
- 假设对从 u 到根的链加 x，v 是其中一个受影响的点，那么 v 的子树和增加了 x\times(dep[v]-dep[u]+1)=x\times dep[v]-x\times(dep[u]-1)
- 那么一个点的子树和就能表示为 a_u\times x+b_u，分别维护 a,b 即可。
- 问题转化为链加，单点查。
子树加，链求和
- 维护每个点到根的和，接下来考虑如何处理子树加。
- 对于一次子树加，只有子树里的点假设对 u 进行子树加 x，v 是其中一个受影响的点，那么 v 到根的和增加了 x\times(dep_u-dep_v+1)=x\times(dep[u]+1)-x\times dep_v
- 那么一个点到根的和就能表示为 a_u\times x+b_u，分别维护 a,b 即可。
- 问题转化为子树加，单点查。
链加，链求和
- 还是维护把每个点到根的和，链加拆成到根的链。
- 对于一次链加，整棵树都会受影响。影响分成两类。
- 假设对从 u 到根的链加 x，v 是其中一个受影响的点。
  1. v$ 为 $u$ 的子孙。那么 $v$ 到根的和增加了 $x\times dep_u
  2. v$ 为 $u$ 的祖先。那么 $v$ 到根的和增加了 $x\times dep_v
  3. 互不为祖先关系。~~我不会。~~
- 所以还是老老实实的写树剖吧。
与树剖做法的比较
- 时间复杂度：链加、链求和问题更优。（少一个 \log）
- 码量：优。
- 思维难度：劣。
- ~~在时间复杂度允许且懒得思考的情况下还是写树剖吧。~~

Edited by r09er_yrj on 11.17