记录编号	311363	评测结果	AAAAAAAAAA
题目名称	2471.[EZOI 2016]源氏的数学课	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.277 s
提交时间	2016-09-24 12:05:12	内存使用	3.34 MiB

#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define Lowbit(x) (x&(-x))
#define LL long long
using namespace std;
const int maxn=100000*2;
int n,m;
LL c[maxn],cplus[maxn];
void Init();
void Update(int x,LL z){
	for(int i=x;i<=n;i+=Lowbit(i)){
		c[i]+=z;
		cplus[i]+=(LL)z*(n-x+1);
	}
}
LL Get_sumplus(int x){
	LL tot=0;
	for(int i=x;i>=1;i-=Lowbit(i))tot=tot+cplus[i];
	return tot;
}
LL Get_sum(int x){
	LL tot=0;
	for(int i=x;i>=1;i-=Lowbit(i))tot=tot+c[i];
	return tot;
}
int main(){
	freopen("overwatch.in","r",stdin);
	freopen("overwatch.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		LL x;scanf("%lld",&x);Update(i,x);
	}
	for(int i=1;i<=m;i++){
		int type,x,y;scanf("%d%d%d",&type,&x,&y);
		if(type==1)Update(x,y);
		else {
			LL tot=0;
			tot=(Get_sumplus(y)-Get_sumplus(x-1));
			tot-=(Get_sum(y)-Get_sum(x-1))*(n-y);
			printf("%lld\n",tot);
		}
	}
}