题目分类：树状数组

题意：

修改原数列，要求维护他前缀和的前缀和。

题解：

使用线段树会超时真是差评。

这个问题转化为，给数列上的从i到n位依次添加1,2,3……n-i+1倍的某个值。

使用差分的方法，修改一段区间，询问的时候询问前缀和。

利用贡献法就可以在树状数组上实现。

程序：

#include<cstdio>
using namespace std;
struct fenwick
{
	long long val[1520000];
	inline void edit(long long x,long long y)
	{
		if(x==0)return;
		while (x<=100000)
		{
			val[x]+=y;
			x+=(x&(-x));
		}
	}
	inline long long query(int x)
	{
		long long ss=0;
		while (x>0)
		{
			ss+=val[x];
			x-=(x&(-x));
		}return ss;
	}
	inline void edit2(long long x,long long y)
	{
		while (x>0)
		{
			val[x]+=y;
			x-=(x&(-x));
		}
	}
	inline long long query2(int x)
	{
		if(x==0)return 0;
		long long ss=0;
		while (x<=100000)
		{
			ss+=val[x];
			x+=(x&(-x));
		}return ss;
	}
}sgt1,sgt2,sgt3;
long long n,m,x1,x2;
long long a[1520000];
char str[1200];
inline void edit(long long x,long long y)
{
	sgt1.edit(x,(x-1)*y);
	sgt2.edit2(n,y);
	sgt2.edit2(x-1,-y);
	sgt3.edit(n,n*y);
	sgt3.edit(x-1,-y*(x-1));
}
inline long long query(long long x)
{
	return (sgt2.query2(x))*x+sgt3.query(x-1);//-sgt1.query(x);
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		edit(i,a[i]);
	}
	for (long long i=1;i<=m;i++)
	{
		scanf("%s",str+1);
		if(str[1]=='Q')
		{
			scanf("%lld",&x1);
			printf("%lld\n",query(x1));
		}
		else
		{
			scanf("%lld %lld",&x1,&x2);
			edit(x1,x2-a[x1]);
			a[x1]=x2;
		}
	}
	return 0;
}