文章

25

粉丝

0

获赞

0

访问

68477

头像
树状数组(区间修改&单点查询)
经验总结
发布于2020年4月20日 22:53
阅读数 2779

给定长度为N的数列A,然后输入M行操作指令。

第一类指令形如“C l r d”,表示把数列中第l~r个数都加d。

第二类指令形如“Q X”,表示询问数列中第x个数的值。

对于每个询问,输出一个整数表示答案。

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], c[N], n, m;
int lowbit(int x){
	return x&(-x);
}
void add(int x, int y){
	for (int i = x; i <= n; i += lowbit(i)){
		c[i] += y;
	}
}
int ask(int x){
	int res = 0;
	for (int i = x; i; i -= lowbit(i)){
		res += c[i];
	}
	return  res;
}
int main(){
	scanf("%d%d\n", &n, &m);
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	getchar();//getchar吃掉回车
	for (int i = 1; i <= m; i++){
		char ch = getchar();
		if (ch == 'C'){
			int l, r, d;
			scanf("%d%d%d\n", &l, &r, &d);
			add(l, d); add(r + 1, -d);
		}
		else if (ch == 'Q'){
			int x;
			scanf(" %d\n", &x);
			printf("%d\n", a[x] + ask(x));
		}
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发