Description
给出了一个序列，你需要处理如下两种询问。
"C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。
"Q a b" 询问[a, b]区间中所有值的和。
Input
第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000.
第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。
接下来Q行询问，格式如题目描述。
Output
对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15 思路：线段树区间更新。 本题代码是很好的线段树区间更新模板：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=;
struct Node
{
LL sum,val;
} node[*maxn]; void pushup(int i)
{
node[i].sum=node[i<<].sum+node[i<<|].sum;
} void pushdown(int i,int m)
{
if(node[i].val)
{
node[i<<].val+=node[i].val;
node[i<<|].val+=node[i].val;
node[i<<].sum+=(LL)node[i].val*(m-(m>>));
node[i<<|].sum+=(LL)node[i].val*(m>>);
node[i].val=;
}
} void build(int l,int r,int i)
{
node[i].val=;
if(l==r)
{
scanf("%I64d",&node[i].sum);
return ;
}
int mid=(l+r)/;
build(l,mid,i<<);
build(mid+,r,i<<|);
pushup(i);
} LL query(int L,int R,int l,int r,int i)
{
if(L<=l&&r<=R)
{
return node[i].sum;
}
int mid=(l+r)>>;
pushdown(i,r-l+);
LL ans=;
if(L<=mid)ans+=query(L,R,l,mid,i<<);
if(mid<R)ans+=query(L,R,mid+,r,i<<|);
pushup(i);
return ans;
} void update(int L,int R,int add,int l,int r,int i)
{
if(L<=l&&r<=R)
{
node[i].sum+=(LL)add*(r-l+);
node[i].val+=add;
return ;
}
pushdown(i,r-l+);
int mid=(l+r)>>;
if(L<=mid)update(L,R,add,l,mid,i<<);
if(mid<R)update(L,R,add,mid+,r,i<<|);
pushup(i);
} int main()
{
int n,q,a,b;
LL c;
while(scanf("%d%d",&n,&q)!=EOF)
{
build(,n,);
char s[];
while(q--)
{
scanf("%s",s);
if(s[]=='C')
{
scanf("%d%d%I64d",&a,&b,&c);
update(a,b,c,,n,);
}
else if(s[]=='Q')
{
scanf("%d%d",&a,&b);
printf("%I64d\n",query(a,b,,n,));
}
}
}
return ;
}