P3368 （模板 ）树状数组2
2021-06-22 20:03
标签：for sum 树状 div end 更新 题解 ons 考题 借这个题学新姿势，这个题需要利用差分才能AC，普通树状树有3个点过不了。 差分原理（参考题解区大佬）： 一个例子，一组数据 $ a[] = { 1, 5, 4, 2, 3 } $，差分后得到 $ b[] = { 1, 4, -1, -2, 1 } $，其中 $ a_0 = 0, b_i = a_i - a_{i - 1} $，求原数组 $ a_n $ 某个位置 $ i $ 上的值。 由 $ b_i = a_i - a_{i - 1} \Rightarrow a_i = b_i + a_{i - 1} $，于是 $$ \left. \begin{aligned} a_i &= b_i + a_{i - 1} \\ a_{i - 1} &= b_{i - 1} + a_{i - 2} \\ \vdots \\ a_1 &= b_1 + a_0 \end{aligned} \right \} + $$ $ \Rightarrow a_i = b_i + b_{i - 1} + \cdots + b_1 + a_0 $ ，注意到 $ a_0 = 0 $，于是 $ a_i = \sum_{i = 1}^{n} b_i $ 。这样就求出了原数组位置上的值了。 然后再看看如何更新区间的值呢。 我们对 a 数组区间 2 ~ 4 每个值进行 +2 操作，得到 $ 1, 7, 6, 4, 3 $，我们对这个数组进行新的差分得到 $ b_n‘ = { 1 6 -1 -2 -1 } $ ，我们比较新的差分数组 $ b_n‘ $ 与 $ b_n $，发现只有 $ b_2‘,b_5‘ $ 上的值变了，$ b_2‘ = b_2 + 2, b_5‘ = b_5 - 2 $，可以验证，在任何区间 $ a[l,...,r] $ 做出 $ +x $ 更新，都有 $ b_l‘ = b_l + x , b_{r + 1}‘ = b_{r + 1} - x $ 。并且不论任何数组经过这样操作都有这样的特点，于是就有了代码中的 `dif()` 函数对区间进行更新。这样每次更新只用更新位置 $ b_l, b_{r + 1} $ 上的值，效率提高了许多。 P3368 （模板 ）树状数组2 标签：for sum 树状 div end 更新 题解 ons 考题 原文地址：https://www.cnblogs.com/darkchii/p/9678063.html#include
下一篇：python - 进程