众所周知：
- 线段树的代码长，常数大；
- 树状数组的代码短，常数小，甚至可以通过 1 0 6 10^6 106 量级的数据。
所以，能不能实现一个可以区间修改、区间查询的树状数组呢？
由于涉及区间操作，考虑差分数组 { d n } \{d_n\} {dn}。
区间修改
对于原数组 [ l , r ] [l,r] [l,r] 区间每个数加 w w w。
可以转化为两次单点修改，即 l l l 单点处加 + w +w +w， r + 1 r+1 r+1 单点处加 − w -w −w。
区间查询
对于原数组 [ l , r ] [l,r] [l,r] 区间求和。
显然 ∑ i = l r a i \sum\limits_{i=l}^r a_i i=l∑rai 可以差分为两个 [ 1 , u ] [1,u] [1,u] 的前缀求和。
∑ i = 1 u a i = ∑ i = 1 u ∑ j = 1 i d j \sum\limits_{i=1}^{u} a_i =\sum\limits_{i=1}^u\sum\limits_{j=1}^{i}d_j i=1∑uai=i=1∑uj=1∑idj
观察每一个 a i = ∑ j = 1 i d j a_i=\sum\limits_{j=1}^{i}d_j ai=j=1∑idj，可以发现
a 1 = d 1 a 2 = d 1 + d 2 a 3 = d 1 + d 2 + d 3 ⋯ a u = d 1 + d 2 + d 3 + ⋯ + d u \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} a1a2a3⋯au=d1=d1+d2=d1+d2+d3=d1+d2+d3+⋯+du
所以 d 1 d_1 d1 的贡献为 u u u， d 2 d_2 d2 的贡献为 u − 1 u-1 u−1， d 3 d_3 d3 的贡献为 u − 2 u-2 u−2，……， d u d_u du 的贡献为 1 1 1。
故可得 d k d_k dk 的贡献为 u − j + 1 u-j+1 u−j+1。
∑ i = 1 u ∑ j = 1 i d j = ∑ j = 1 u d j ( 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) i=1∑uj=1∑idj=j=1∑udj(u−j+1)
发现 u + 1 u+1 u+1 的值是固定的，可以提取出来：
∑ j = 1 u d j ( u − j + 1 ) = ( ( u + 1 ) ∑ j = 1 u d j ) − ( ∑ j = 1 u ( j × d j ) ) \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) j=1∑udj(u−j+1)=((u+1)j=1∑udj)−(j=1∑u(j×dj))
因此同时使用两个树状数组维护 { d n } \{d_n\} {dn}、 { n × d n } \{n\times d_n\} {n×dn} 即可，该技巧即为超级树状数组。
代码实现
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);
}