树状数组模板

树状数组其实和线段树是一个东西只不过线段树时间复杂度会快一点

作用都是：单点修改和区间查询

线段树传送门

例题：P3374 【模板】树状数组 1

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

• 将某一个数加上 xx

• 求出某区间每一个数的和

#include 
using namespace std;
int n, m, tree[500005];

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

inline void update(int x, int y) {
	while (x <= n) {
		tree[x] += y, x += lowbit(x);
	}
}

inline int getsum(int x) {
	int sum = 0;
	while (x) {
		sum += tree[x];
		x -= lowbit(x);
	}
	return sum;
}

主函数要随机应变

key words

update(x, y); //把x变为y

getsum(x);//求和

#include 
using namespace std;
int n, m, tree[500005];
inline int lowbit(signed x) {
	return x & -x;
}
inline void update(int x, int y) {
	while (x <= n) {
		tree[x] += y, x += lowbit(x);
	}
}
inline int getsum(int x) {
	int sum = 0;
	while (x) {
		sum += tree[x];
		x -= lowbit(x);
	}
	return sum;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		update(i, a);
	}
	for (int i = 1; i <= m; i++) {
		int n, x, y;
		cin >> n >> x >> y;
		if (n == 1) update(x, y);
		else cout << getsum(y) - getsum(x - 1) << endl;
	}
	return 0;
}