树状数组常用于高效求解前缀和、区间和，复杂度都在$O(logn)$，同时支持单点更新。但是区间更新效率低下，朴素的实现需要对区间内的每一个元素实行单点更新，时间复杂度在$O(n)$。可以通过维护两个数组，来高效地实现区间更新。
假设目前有一列数据$a_1, a_2, a_3, …, a_n$，用两个树状数组来高效进行这些数据的区间更新与求和。令sum(bit, i)是树状数组bit的前i项和，构建两个树状数组bit0和bit1，并且假设数列${a_i}$的前i项和为
其中树状数组bit0代表的是原数组，bit1代表的原数组上的区间更新量。那么在$[l, r]$区间上同时加上$x$就可以看成是：
- 在bit0的$l$位置上加上$-x(l - 1)$
- 在bit1的$l$位置上加上$x$
- 在bit0的$r+1$位置上加上$xr$
- 在bit1的$r+1$位置上加上$-x$
下面考虑三种情况，来验证上面的更新策略，假设要求数组a的前i项和：
- $i < l$：不影响
- $l \le i \le r$：相当于加上了$x * i - x(l - 1) = x * (i - l + 1)$，正确
- $l > r$：相当于加上了$0 * i + xr - x(l - 1) = x * (r - l + 1)$，正确
基于c++的代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31const int MAX_N = 100001;
int bit0[MAX_N], bit1[MAX_N];
int sum(int* bit, int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= i & (-i);
}
return res;
}
void add(int* bit, int i, int x) {
while (i <= MAX_N) {
bit[i] += x;
i += i & (-i);
}
}
// 求和[1, i]
int sum(int i) {
return sum(bit1, i) * i + sum(bit0, i);
}
// 区间更新，[from, to]的元素都加上x，时间复杂度logn
void rangeUpdate(int from, int to, int x) {
add(bit0, from, -x * (from - 1));
add(bit1, from, x);
add(bit0, to + 1, x * to);
add(bit1, to + 1, -x);
}