ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study【树状数组】

传送门：传送门

给你一个a数组

定义l~r之前的区间和为：

有两种操作：

1 . 查询l~r之前的区间和

0 . 改变第l个数为r

单点修改区间查询 可以用树状数组和线段树来做，我贴的代码是树状数组的

思路：

首先将数组逆序化， 然后进行一个建立两个树状数组， 一个为 a[i], 一个为 i*a[i]，我们要求的区间和为l~r，逆序化后就变成了，（n-r+1）~（n-l+1）之前的区间和，我们要求的式子就可以化成

i*a[i]的(n-r+1)~(n-l+1)的区间和 减去 【n-1+(n-l+1)】(即为l)*a[i]的(n-r+1)~(n-l+1)的区间和.

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn  100005
ll tree1[maxn], tree2[maxn];
int n, m;
ll a[maxn];
int lowbit(int x) {
	return x&(-x);
}
void creattree1(int x,ll int v) {
	for(int i = x; i <= n; i += lowbit(i)) {
		tree1[i] += v;
	}
	return ;
}
void creattree2(int x, ll v) {
	for(int i = x; i <= n; i+=lowbit(i)) {
		tree2[i] += v;
	}
	return ;

}
ll getsum1(int x) {
	ll ans = 0;
	for(int i = x; i > 0; i -= lowbit(i)) {
		ans += tree1[i];
	}
	return ans;
}
ll getsum2(int x) {
	ll ans = 0;
	for(int i = x; i > 0; i -= lowbit(i)) {
		ans += tree2[i];
	}
	return ans;
}
int main() {
	while(~scanf("%d%d",&n,&m)) {
		memset(tree1,0,sizeof(tree1));
		memset(tree2,0,sizeof(tree2));
		for(int i = n; i > 0; i--) {
			scanf("%lld",&a[i]);
		}
		for(int i = 1; i <= n; i++) {
			creattree1(i,a[i]);
			creattree2(i,i*a[i]);
		}
		for(int i = 0; i < m; i++) {
			int q, l, r;
			scanf("%d%d%d", &q,&l,&r);
			if(q==1) {
				int x = n - r + 1;
				int y = n - l + 1;
				ll ans1 = (getsum1(y) - getsum1(x-1))*(x-1);
				ll ans2 = getsum2(y) - getsum2(x-1);
				ll ans = ans2 - ans1;
				printf("%lld\n",ans);
			} else {
				int z = n - l + 1;
				ll ans = r - a[z];
				a[z] = r;
				creattree1(z, ans);
				creattree2(z, z*ans);
			}
		}
	}
	return 0;
}