树状数组

例题

洛谷P3374【模板】树状数组1

主要思路

参考大佬的博客

代码

#include 
#include 
using namespace std;

int d[500001];
int n, m, x, y, k, com;

int lowbit(int x){  // 树状数组主要函数 
	return x & (-x);
}

int src(int x){ // 1~x区间和查询 
	int ans = 0;
	while(x){
		ans += d[x];
		x -= lowbit(x);
	}
	return ans;
}

void add(int x, int v){ // x位置数据更新,d[x]+v
	while(x <= n){
		d[x] += v;
		x += lowbit(x);
	}
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		int in;
		cin >> in;
		add(i, in); // 初始化 
	}
	for(int i = 0; i < m; i++){
		scanf("%d", &com);
		if(com == 1){
			scanf("%d %d", &x, &k);
			add(x, k);
		}
		else if(com == 2){
			scanf("%d %d", &x, &y);	
			printf("%d\n", src(y) - src(x-1));  
		}
	}
}