当 BIT 遇到 DFS 序

众所周知，当一棵树求出 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

文章操作

相关推荐

评论

当 BIT 遇到 DFS 序