树状数组专题

本文将以单点更新、区间求和开启树状数组的新世界。
—————————————————持续更新~———————————————————

同样是数组模拟树形结构，树状数组常和线段树比较优劣，放心，下面保证一字不提线段树，文末会有链接传送，专门比较树状数组和线段树。

还是先感谢优秀博客（写的十分详细了，这里只作总结）：
树状数组详解

树状数组实现单点更新、区间求和

算法思想

  1. 数组A[]记录原数据， C[]表示我们的树状数组（数组长度和 A[]相同），数组的首位都遗弃
    因为C[]的构建和二进制密切相关，下面的数均用二进制表示
  2. 构建过程：
    • C[1] = A[1];
    • C[10] = A[1] + A[10];
    • C[11] = A[11];
    • C[100] = A[1] + A[10] + A[11] + A[100];
    • C[101] = A[101];
    • C[110] = A[101] + A[110];
    • C[111] = A[111];
    • C[1000] = A[1] + A[10] + A[11] + A[100] + A[101] + A[110] + A[111] + A[1000];

好了用二进制确实麻烦，后面还是回归十进制表示。这其实是有规律的，直接ctrl+v优秀博客里的了

  • $C[i] = A[i - 2^k+1] + A[i - 2^k+2] + … + A[i];$ //k为i的二进制中从最低位到高位连续零的长度
  • 如对于C[6],二进制110低位开始有一个连续零，k取1，C[6]=A[5]+A[6]
  • 我们先把k的问题放一边，假设C[]已经构建好了，前i项的和 Sum[i]这样得到：
    $$Sum[i] = C[i] + C[i-2^{k1}] + C[(i - 2^{k1}) - 2^{k2}] + …$$
    同样如Sum[6]，二进制110的k取1， 二进制100的k取3，Sum[6] = C[6]+ C[4];
  • 如何对C[i]求对应的k是关键，k的引入让人不仅赞美位运算的优雅。
  1. lowbit(int i)计算C[i]对应的$2^k$（于是lowbit取i的二进制中从低位到高位首次出现1的位置）
  • 先给出最优答案i&(-i)
  • 仍然举C[6]的例子，二进制110对应的$2^k$为010，其实可以根据要求推出来;
    只需保留低位到高位首次出现的1即可：i&(~(i-1))
    因为-i就是i-1再取反（负数的补码知识，设想一下全为1时的二进制数表示-1），所以得到最优答案i&(-i)
    搞定了lowbit()离成功就不远了~（费这么大劲求个区间和时间复杂度必须O(log n)）

***注：更新A[i]时根据公式更新C[],计算 Sum[i]时也要利用lowbit()
———————————————————核心代码———————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[100005], c[100005];
int lowbit(int x){
	return x&(-x);
}
void update(int i, int temp){//i的位置上增加值temp
	while(i <= n){
		c[i] += temp;
		i += lowbit(i);
	}
}
int getsum(int i){//求Sum(i)
	int res = 0;
	while(i > 0){
		res += c[i];
		i -= lowbit(i);
	}
	return res;
}

代码很短，实现了单点更新，区间查询[x,y]直接Sum(y)-Sum(x-1)即可。

树状数组区间更新、区间求和

  • 上面的update()只是针对单点更新，如果要对某个区间的值更新（如全加上某个值、减去某个值），需要引入差分的思想，D[]不断做差分 D[i] = A[i] - A[i-1]；

直接借用人家优秀博客的例子吧：

A[] = 1 2 3 5 6 9
D[] = 1 1 1 2 1 3
如果我们把[2,5]区间内值加上1，则变成了
A[] = 1 3 4 6 7 9
D[] = 1 2 1 2 1 2
仅改变D[2]和D[6]的位置即可

  • 于是之前写的代码都还有用，只是用D[]替换了 A[],在开始输入 A[]更新时的update(i, a[i])改为update(i, a[i]-a[i-1])， 对于要更新的区间[x,y]增加
    update(x, temp); update(y+1, -temp);

  • 显然此时Sum(i)求的是更新后单个A[i]的值了，但已经O(log n)实现了区间更新、单值查询了

  • 要区间求和还需继续利用差分，后面就是纯公式推导了

$Sum(n) = A[1] + A[2] + … + A[n]
= (D[1]) + (D[1]+D[2]) + … + (D[1]+D[2]+…+D[n])
= nD[1] + (n-1)D[2] + … + 1D[n]
= n(D[1]+D[2]+…+D[n]) - (0D[1]+1D[2]+…+(n-1)D[n])
= n\sum_{i=1}^{n}{D[i]} - \sum_{i=1}^{n}{D[i](i-1)}$

于是又用两个数组sum1[] sum2[]替代了 D[]
—————————————————完整代码—————————————————————

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>

using namespace std;

typedef long long ll;
int n;
ll sum1[500005];//D[1]+D[2]+...+D[N]
ll sum2[500005];//0*D[1] + 1*D[2] + ... + (n-1)*D[n]
ll a[500005];
int lowbit(int x){
	return x&(-x);
}
void update(int i, ll temp){
	int x = i;
	while(i <= n){
		sum1[i] += temp;
		sum2[i] += (x-1)*temp;
		i += lowbit(i);
	}
}
ll getsum(int i){
	ll res = 0;
	int x = i;
	while(i > 0){
		res += (x*sum1[i] - sum2[i]);//sum[i]
		i -= lowbit(i);
	}
	return res;
}
int main(){
	int m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &a[i]);
		update(i, a[i]-a[i-1]);
	}
	while(m--){

		int x, y;
		scanf("%d%d", &x, &y);
		cout << getsum(y)-getsum(x-1) <<endl;
	
	}
	return 0;
}