#C/C++#树状数组模板

问题模型

现在有一个这样的问题：有一个数组a，，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和。

这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间复杂度，而查询的话是O(n)的复杂度，总体时间复杂度为O(qn)

可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是O(1)的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是O(n)，总体时间复杂度还是O(qn)。

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

lowbit函数

int lobit(int k) {
	return k & (-k);
}

树状数组

这是树状数组的模型

可以看出

C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8

所以他就变成logn的数据结构了

模板

树状数组 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1： 格式：1 x k 含义：将第x个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1：

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

14
16

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t);
	}
   	for(int i = 1;i <= m;++i) {
   		int t,x,y;
   		cin >> t >> x >> y;
   		if(t == 1) add(x,y);
   		if(t == 2) cout << sum(y) - sum(x-1) << endl;
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}

树状数组 2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x 含义：输出第x个数的值

输出格式：

输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例#1：

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

6
10

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 
int low;

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t - low);
   		low = t;
	}
   	for(int i = 1;i <= m;++i) {
   		int t;
   		cin >> t;
   		if(t == 1) {
   			int x,y,s;
   			cin >> x >> y >> s;
   			add(x,s);
   			add(y + 1,-s);
		}
   		if(t == 2) {
   			int s;
   			cin >> s;
   			cout << sum(s) <<endl;
		}
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}