树状数组

学习
字数统计: 1.8k   |   阅读时长≈ 8 分钟

树状数组

1. 概述

  • 树状数组：动态维护前缀和，其应用为：
    1. 单点修改，区间查询
    2. 区间修改，单点查询（通过差分思想）
    3. 区间修改，区间查询（直接线段树了，不用树状数组表示）

2. 前置

  • $lowbit()$ 运算：非负整数在二进制表示下最低位 $1$ 及其后面的 $0$ 构成的数值
  • 例如：$lowbit(44)=lowbit((101100)_2)=4$
  • 在计算机中为了得到这个数值，可以先对 $101100$ 按位取反再 $+1$ 得到 $010100$，并把两个数字相与，即可得到 $100$。
  • ① ~n+1=-n (表示按位取反)，② lowbit(n)=n&(n+1)=n&-n
  • 下图为树状数组结构
image-20230727151151406

3. 性质

  • 注意：线段树是树状数组的扩展，比树状数组的功能更强，但对于比较一般的问题更倾向于比较简单的树状数组
  • 下图为树状数组展开为二进制

image-20230727153114410

  • 如果不好理解这个图的形状，可以这样来看：
  • 1）$len=1$ 代表第 $0$ 层，从 $2^0$ 开始，两两元素的差值为 $2^1$
  • 2）$len=2$ 代表第 $1$ 层，从 $2^1$ 开始，两两元素的差值为 $2^2$
  • 3）···
  1. 性质一、$t[x]$ 节点的长度等于 $lowbit(x)$ ，比如 $t[5]$ 的长度为 $lowbit((0101)_2)=1$
  2. 性质二、$t[x]$ 节点的父节点等于 $t[x+lowbit(x)]$ ，比如 $t[6]$ 的父节点为 $t[6+lowbit(6)]=t[6+lowbit(0110)_2]=t[8]$
  3. 性质三、$t[x]$ 节点左上角的值等于 $t[x-lowbit(x)]$ ，此性质用于求和
  4. 性质四、整棵树的深度为 $log_2^{n+1}$
  5. 性质五、树状数组中每个元素的值存储的都是 $c[x]=[x-lowbit(x), x]$ 这个区间内元素的和 ，由此可推导
image-20230727153359531

4. 操作

4.1. 单点修改，区间查询

1
2
3
int lowbit(int x) {
    return x&(-x);
}
image-20230727154039606
  • 在执行 $add$ 操作时，我们要对 $t$ 数组的某个值 $+k$ ，比如 $t[3]+k$，则需要更新其父节点 $t[4],t[8]$ 也加上$k$ ，根据性质 $2$ ，我们可以通过 $t[3+lowbit(3)]找到t[4]$，再通过 $t[4+lowbit(4)]$ 找到 $t[8]$，让三个节点都加上 $k$ 即可。
1
2
3
4
5
int add(int x,int k) {
    // n是a数组的长度
    for(int i=x;i<=n;i+=lowbit(i))
        t[i]+=k;
}
image-20230727154547790
  • 如果我们要求某个区间的和，比如 $ask(7)$ ，从图中可以看出$[1,7]$ 的和等于 $t[7]+t[6]+t[4]$（不断加左上角的值）[性质三]，其中 $t[7]=a[7]$ ，$t[6]=t[5]+a[6]=a[5]+a[6]$，$t[4]=t[2]+t[3]+a[4]=t[1]+a[2]+a[3]+a[4]=a[1]+a[2]+a[3]+a[4]$，所以为 $[a[1],a[7]]$ 的元素和。
1
2
3
4
5
6
7
int ask(int x) {
    int sum=0;
    for(int i=x;i;i-=lowbit(x)) {
        sum+=t[i];
    }
    return sum;
}
  • 当然，上述函数只能求 $1$ 到 $n$ 的区间和，如何求 $l$ 到 $r$ 的区间和呢？可以利用前缀和的性质：$[L,R]=[1,R]-[1,L-1]$
1
2
3
4
5
6
7
8
int search(int l,int r) {
    int res=0;
    for(int i=l-1;i;i-=lowbit(i))
        res-=t[i];
    for(int i=r;i;i-=lowbit(i))
        res+=t[i]
    return res;
}
  • 板子题如下：

题目链接：P3374 【模板】树状数组 1 

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
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
const int maxn=5e5+5;
int n,m; // n是数组大小,m为查询次数
int t[maxn]; // t数组
int lowbit(int x) {
	return x&(-x); // 详见文档
}
int add(int x,int k) {
	for(int i=x;i<=n;i+=lowbit(i)) {
		t[i]+=k;
	}
}
// [L,R]=[1,R]-[1,L-1]
long long search(int l,int r) {
	long long res=0;
	for(int i=r;i;i-=lowbit(i)) {
		res+=t[i];
	}
	for(int i=l-1;i;i-=lowbit(i)) {
		res-=t[i];
	}
	return res;
}
using namespace std;
	int main() {
	cin>>n>>m;
	int temp;
	// 把赋初值操作看成向空白的t数组add值,直接得到t数组,而无需存储a数组
	for(int i=1;i<=n;i++) {
		cin>>temp;
		add(i,temp);
	}
	int op,l,r;
	while(m--) {
		cin>>op;
		if(op==1) {
			cin>>l>>r;
			add(l,r);
		} else if(op==2) {
			cin>>l>>r;
			cout<<search(l,r)<<'\n';
		}
	}
	return 0;
}
/*
输入样例:
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出样例:
14
16
*/

4.2. 区间修改，单点查询

  • lowbit(x)函数
1
2
3
int lowbit(int x) {
    return x&(-x);
}
  • 区间update函数
1
2
3
4
5
6
// pos:修改点的起始位置,k:更新值
// 对于区间修改,比如[L,R]+k,只需要更新差分数组add(l,k),add(R+1,-k)
void update(int pos,int k) {
	for(int i=pos;i<=n;i+=lowbit(i)) 
		t[i]+=k;
}
  • 为了能对区间进行修改，我们引入差分数组 d[maxn]，要使t[L,R]+k，只需要add(l,k)，add(r+1,-k)，从l起的位置+k，从r+1后的位置-k，利用差分数组的性质
  • 单点ask的函数
1
2
3
4
5
6
7
// 返回区间1~pos的总和
long long ask(int pos) {
	long long res=0;
	for(int i=pos;i;i-=lowbit(i)) 
		res+=t[i];
	return res;
}

  • 只需要将差分数组的 $[1,pos]$ 位相加起来，得到的就是这一位上的值

  • 板子题：洛谷-p3368

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int a[maxn];
int t[maxn]; // 树状数组
int d[maxn]; // 差分数组,用于区间修改,d[i]=a[i]-a[i-1]
int n,m; // n是数列个数,m是操作次数
int lowbit(int x) {
	return x&(-x);
}
// pos:修改点的起始位置,k:更新值
// 对于区间修改,比如[L,R]+k,只需要更新差分数组add(l,k),add(R+1,-k)
void update(int pos,int k) {
	for(int i=pos;i<=n;i+=lowbit(i)) 
		t[i]+=k;
}
// 返回区间1~pos的总和
long long ask(int pos) {
	long long res=0;
	for(int i=pos;i;i-=lowbit(i)) 
		res+=t[i];
	return res;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		d[i]=a[i]-a[i-1];
		update(i,d[i]); // 为t[i]赋初值
	}
	int op,l,r,val,q;
	while(m--) {
		cin>>op;
		if(op==1) {
			cin>>l>>r>>val;
			update(l,val);
			update(r+1,-val);
		} else if(op==2) {
			cin>>q;
			cout<<ask(q)<<'\n';
		}
	}
	return 0;
}
  • AcWing 1264：该题是一个树状数组板子题
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 最普通的树状数组模板

const int N=1e5+5;
int n,m;
int a[N],tr[N];

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

void add(int x,int v) {
	for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}

int query(int x) {
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res+=tr[i];
	return res;
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	
	for(int i=1;i<=n;i++) add(i,a[i]); // 在第i个位置加上a[i]以初始化
	while(m--) {
		int k,x,y;
		cin>>k>>x>>y;
		if(k==0) cout<<query(y)-query(x-1)<<endl; // 区间求和
		else add(x,y); // 单点修改
	}
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信