超级树状数组

众所周知： - 线段树的代码长，常数大； - 树状数组的代码短，常数小，甚至可以通过 $10^6$ 量级的数据。 所以，能不能实现一个可以**区间修改、区间查询**的树状数组呢？ --- 由于涉及区间操作，考虑**差分**数组 $\{d_n\}$。 ### 区间修改 对于原数组 $[l,r]$ 区间每个数加 $w$。 可以转化为两次单点修改，即 $l$ 单点处加 $+w$，$r+1$ 单点处加 $-w$。 ### 区间查询 对于原数组 $[l,r]$ 区间求和。 显然 $\sum\limits_{i=l}^r a_i$ 可以差分为两个 $[1,u]$ 的前缀求和。 $$ \sum\limits_{i=1}^{u} a_i =\sum\limits_{i=1}^u\sum\limits_{j=1}^{i}d_j $$ 观察每一个 $a_i=\sum\limits_{j=1}^{i}d_j$，可以发现 $$ \begin{aligned} a_1&=d_1\\ a_2&=d_1+d_2\\ a_3&=d_1+d_2+d_3\\ \cdots\\ a_u&=d_1+d_2+d_3+\cdots+d_u \end{aligned} $$ 所以 $d_1$ 的贡献为 $u$，$d_2$ 的贡献为 $u-1$，$d_3$ 的贡献为 $u-2$，……，$d_u$ 的贡献为 $1$。 故可得 $d_k$ 的贡献为 $u-j+1$。 $$ \sum\limits_{i=1}^u\sum\limits_{j=1}^{i}d_j=\sum\limits_{j=1}^{u}d_j(u-j+1) $$ 发现 $u+1$ 的值是固定的，可以提取出来： $$ \sum\limits_{j=1}^{u}d_j(u-j+1)=\Big((u+1)\sum\limits_{j=1}^{u}d_j\Big)-\Big(\sum\limits_{j=1}^{u}(j\times d_j)\Big) $$ 因此同时使用两个树状数组维护 $\{d_n\}$、$\{n\times d_n\}$ 即可，该技巧即为超级树状数组。 ### 代码实现 ```cpp typedef long long lint; lint sum(int p, lint *t) { // 查询 t 中 [1,p] 之和 lint res = 0; for (int i = p; i; i -= lowbit(i)) res += t[i]; return res; } lint ask(int p) { return sum(p, d) * (p + 1) - sum(p, f); } lint query(int l, int r) { return ask(r) - ask(l - 1); } void add(int p, lint x, lint *t) { for (int i = p; i <= n; i += lowbit(i)) t[i] += x; } void update(int l, int r, lint x) { add(l, x, d), add(r + 1, -x, d); add(l, x * l, f); add(r + 1, -x * (r + 1), f); } ```