树状数组讲解_构建树状数组的时间复杂度

简介

首先我们搞明白树状数组是用来干嘛的.现在有一个这样的问题：
有一个数组a，下标从0到n-1，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值，查询的话是查询数组中任意一个区间的和，w + q < 500000。

1.朴素做法:
修改是O (1) 的时间复杂度，而查询的话是O (n)的复杂度，总体时间复杂度为O (qn) ；
2.前缀和:
查询的话是O (1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O ( n ) 总体时间复杂度还是O(qn)。

可以发现，两种做法中，要么查询是O(1)，修改是O(n)；要么修改是O(1)，查询是O ( n )。
那么就有没有一种做法可以综合一下这两种朴素做法，然后整体时间复杂度可以降一个数量级呢？有的，对，就是树状数组。

lowbit函数

这里我们先不管树状数组这种数据结构到底是什么，先来了解下lowbit这个函数，你也先不要问这个函数到底在树状数组中有什么用；

lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1.
举个例子:x = 6，它的二进制为110，那么lowbit(x)就返回2，因为最后一位1表示2。
1
2

对于一个数的负数的补码就等于对这个数取反+1
将十进制的 -12 转换为二进制 10001100
（最高位代表符号,负数为1,正数为0；后7位数值）
取反=11110011
然后+1 =1111 0100
即补码为1111 0100
原码 0000 1100
补码 1111 0100
0000 0100

int lowbit(x){return x&(-x);}
1

树状数组的原理

树状数组的性质:
1.每个节点都保存以它为根的子树中所有 叶节点的和。
2.每个节点的子节点的个数等于lowbit(x)的位数.
3.除树根外每个节点的父节点是x+lowbit(x);

单点修改，区间查询

下面是二进制版本，能看到
更新过程是每次加了个二进制的低位1(101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000)

查询过程每次就是去掉了二进制中的低位1(1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000)

单点更新:

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    tree[x] = tree[x] + k;
    x = x + lowbit(x);
  }
}
1
2
3
4
5
6

前缀求和

int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x >= 1) {
    ans = ans + tree[x];
    x = x - lowbit(x);
  }
  return ans;
}
1
2
3
4
5
6
7
8

区间求和

int queary(int l,int r){
	return getsum(r)-getsum(l-1);
}
1
2
3

注意：lowbit(0)=0,所以x=0时，x+=lowbit(x)或x-=lowbit(x),x仍为0.

区间修改+单点查询

区间修改给某个区间[x,y]同时加上某个值，然后查询某个点的值，或者某个区间的值。这时候需要差分建树。

原数组       1 2 3 3   2  1
差分数组     1 1 1 0  -1 -1
1
2

差分数组区间[1,x]前缀和，就是原数组x的单点值，而区间修改只需要修改单点x和y+1.
例如：区间[2,4]加2

更新后数组	:  1 4 5 5  2  1
更新后差分数组: 1 3 1 0 -3 -1
原差分数组      1 1 1 0  -1 -1
我们发现差分数组只有2和5的位置发生改变
1
2
3
4

void add(int x, int k){ //这个函数用来在树状数组中直接修改
    while(x <= n) tree[x] += k, x+=lowbit(x);
}
void range_add(int l, int r, int x){ //给区间[l, r]加上x
    add(l, x), add(r + 1, -x);
}
int ask(int x){ //单点查询
    int res = 0;
    while(x) res +=tree[x], x-=lowbit(x);
    return res;
}
void read(){
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(i,a[i]-a[i-1]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

区间修改+区间查询

由上面可知，差分数组区间[1,x]前缀和，就是原数组x的单点值。原区间[1,x]的前缀和：

更新后数组	:  1 4 5 5  2  1
更新后差分数组: 1 3 1 0 -3 -1
比如：我们要求区间[1,3]的和，我们发现第一个位置用了3次，第二个位置用了2次，第三个位置用了1次.
我们可以通过每个位置先乘以x(在这里x=3)，然后再减去(i-1)*a[i]个.
1
2
3
4

相当与维护2个树状数组一个是a[i],另一个是b[i]=(i-1)*a[i].

void add(int x,int t){
	int k=x;
	while(x<=n){
	a[x]+=t;
	b[x]+=(k-1)*t;
	x+=lowbit(x);
	}
}
int query(int x)
{
	int ans=0,k=x;
	while(x>0){
	ans+=k*a[i]-b[i];
	x-=lowbit(x);
	}
	return ans;
}
void range_add(int l, int r, int x){
    add(l, x), add(r + 1, -x);
}

注意:运算范围超int时要用long long;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22