众所周知：
- 线段树的代码长，常数大；
- 树状数组的代码短，常数小，甚至可以通过 \(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\}\) 即可，该技巧即为超级树状数组。
代码实现
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);
}