Description

Input

Output

Sample Input

Sample Output

你将可以对它们进行两种操作，一种是对于当前给定区间里的数字都加上一个数，还有一种是对于当前给定区间里的数字进行求和。

处理例如以下:假设给区间[l,r]都加上一个数x的话，我们令s(i)=加上x之前的前i项和，s’(i)=加上x之后的前i项和，那么就有当i<l时，s’(i)=s(i);当l<=i<=r时。s’(i)=s(i)+x*(i-l+1)=s(i)+x*i
-x*(l-1);当i>r时，s’(i)=s(i)+x*(r-l+1)。那么我们就能够建立两个树状数组，从而将问题简化。详细參见：csdn博客：http://blog.csdn.net/u013068502/article/details/47252335。

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxn = 100005;
LL bit1[maxn], bit2[maxn]; // 代表两个树状数组。数组1用来存储初始值，
						   // 数组2用来存储变化的值
int n, query; // 初始数组大小。问题的个数
char op[5]; // 选择哪种操作

int lowbit(int x);
void update(LL * bit, int x, int add);
LL sum(LL * bit, int x);

int main()
{
	ios::sync_with_stdio(false);
	int a, b, c, x;
	while (~scanf("%d%d", &n, &query))
	{
		memset(bit1, 0, sizeof(bit1));
		memset(bit2, 0, sizeof(bit2));
		// 上面清空数组。避免上次结果干扰
		for (int i=1; i<=n; i++)
		{
			scanf("%d", &x);
			update(bit1, i, x); // 将初始值存入数组1
		}
		while (query--)
		{
			scanf("%s%d%d", op, &a, &b);
			if (op[0] == 'C')
			{
				scanf("%d", &c);
				update(bit1, a, (-c)*(a-1));
				update(bit2, a, c);
				// 上面更新改变状态
				update(bit1, b+1, c*b);
				update(bit2, b+1, (-c));
				// 上面去掉反复状态
			}
			else
			{
				LL ans = 0;
				ans += sum(bit1, b)+sum(bit2, b)*b;
				ans -= sum(bit1, a-1)+sum(bit2, a-1)*(a-1);
				printf("%lld\n", ans);
			}
		}
	}
	return 0;
}

int lowbit(int x) // 求2^k，k表示x为二进制时末尾的0的个数
{
	return (x&(-x));
}

void update(LL * bit, int x, int add)
{ // 更新节点信息(加上数add)
	while (x!=0 && x<=n)
	{
		bit[x] += add;
		x += lowbit(x);
	}
}

LL sum(LL * bit, int x)
{ // 区间求和(求1~x之间数组的和)
	LL res = 0;
	while (x > 0)
	{
		res += bit[x];
		x -= lowbit(x);
	}
	return res;
}