文章

25

粉丝

0

获赞

0

访问

244707

头像
树状数组(区间修改&区间查询)
经验总结
发布于2020年4月20日 23:36
阅读数 9504

给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:

1、“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”,表示询问 数列中第 l~r 个数的和。

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

#include<iostream>
using namespace std;
const int N = 2e5;
typedef long long ll;
ll c1[N], c2[N], n, m;
ll a[N];
ll lowbit(ll x){
	return x&(-x);
}
void add(ll x, ll y){
	for (ll i = x; i <= n; i += lowbit(i)){
		c1[i] += y; c2[i] += x*y;
	}
}
ll ask(ll x){
	ll res = 0;
	for (ll i = x; i; i -= lowbit(i)){
		res += (x + 1)*c1[i] - c2[i];
	}
	return res;
}
int main(){
	scanf("%lld%lld", &n, &m);
	for (ll i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
		add(i, a[i] - a[i - 1]);
	}
	getchar();
	for (int i = 1; i <= m; i++){
		char ch = getchar();
		if (ch == 'C'){
			ll l, r, d;
			scanf("%lld%lld%lld", &l, &r, &d);
			getchar();
			add(l, d); add(r + 1, -d);
		}
		else if (ch == 'Q'){
			ll x, y;
			scanf("%lld%lld", &x, &y);
			getchar();
			printf("%lld\n", ask(y) - ask(x - 1));
		}
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发