You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b” means querying the sum of Aa, Aa+1, … , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
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
Hint
The sums may exceed the range of 32-bit integers.
您有N个整数A1，A2，…，AN。 您需要处理两种操作。 一种操作类型是在给定间隔内向每个数字添加一些给定数字。 另一种是在给定的时间间隔内求和。
输入值
第一行包含两个数字N和Q。1≤N，Q≤100000。
第二行包含N个数字，即A1，A2，…，AN的初始值。 -1000000000≤Ai≤1000000000。
接下来的每条Q线代表一个操作。
“ C a b c”是指将c加到Aa，Aa + 1，…，Ab中的每一个上。 -10000≤c≤10000。
“ Q a b”是指查询Aa，Aa + 1，…，Ab的和。
输出量
您需要依次回答所有Q命令。 一行回答。
输入
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
输出
4
55
9
15
提示
总和可能超出32位整数的范围。
题目大意：
输入n和m，表示n个数和m个询问，对于每个询问：
- “ C a b c”是指将c加到Aa，Aa + 1，…，Ab中的每一个上。 -10000≤c≤10000。
- “ Q a b”是指查询Aa，Aa + 1，…，Ab的和。
当遇到Q的时候输出区间的和。
解题思路：
这道题是线段树的一道区间求和和区间更新，因为在区间更新时，普通遍历线段树一定会超时，我们这里用一个lazy数组用于存放要更新的值，每次用到这个值的时候再分配到子节点，我们什么时候用到这个区间什么时候就把lazy的值下放到子节点，举个例子，比如一共有12个数，第一次给 [ 1 6 ] 每一个加3，就让这个节点的lazy值为3，就不往下放了，当再次操作和1-6区间有重合时，再把这个节点的lazy值下放到子节点。关于lazy数组：因为一个树中有好几个元素，所以我们用结构体存储这棵树，我们要存放当前节点的值，当前节点的lazy值和区间长度，为什么要存区间长度，因为在给这个点的lazy赋值时，这个点的和一定会加上区间长度*lazy值，因为区间长度即是要更新值的个数。就一定不会超时。AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll _max=1e5+50;
ll arr[_max];
struct ttt
{
ll lazy,sum;
int len;
}tree[5*_max];
int main()
{
void build_tree(int,int,int);
ll query(int,int,int,int,int);
void update(int,int,int,int,int,int);
int n,m;
scanf("%d%d",&n,&m);
for ( int i = 0; i < n; i++)
scanf("%lld",&arr[i]);
getchar();
build_tree(0,0,n-1);
while(m--)
{
char k;
int a,b,c;
scanf("%c",&k);
if(k=='Q')
{
scanf("%d%d",&a,&b);
getchar();
ll sum=query(0,0,n-1,a-1,b-1);
printf("%lld
",sum);
}
else
{
scanf("%d%d%d",&a,&b,&c);
getchar();
update(0,0,n-1,a-1,b-1,c);
}
}
//system("pause");
return 0;
}
void build_tree(int node ,int start ,int end)
{
tree[node].lazy=0;
tree[node].len=end-start+1;
if(start==end)
{
tree[node].sum=arr[start];
return;
}
int ln = node*2+1;
int rn = node*2+2;
int mid=(start+end)>>1;
build_tree(ln,start,mid);
build_tree(rn,mid+1,end);
tree[node].sum=tree[ln].sum+tree[rn].sum;
}
void lazzy(int node)
{
if(tree[node].lazy)
{
tree[node*2+1].lazy+=tree[node].lazy;
tree[node*2+2].lazy+=tree[node].lazy;
tree[node*2+1].sum+=tree[node].lazy*tree[node*2+1].len;
tree[node*2+2].sum+=tree[node].lazy*tree[node*2+2].len;
tree[node].lazy=0;
}
}
ll query(int node, int start, int end, int l, int r)
{
if (l<=start&&r>=end)
return tree[node].sum;
lazzy(node);
int ln=node*2+1;
int rn=node*2+2;
int mid=(start+end)>>1;
ll suml,sumr;
suml=sumr=0;
if(l<=mid)
suml=query(ln,start,mid,l,r);
if(r>mid)
sumr=query(rn,mid+1,end,l,r);
return suml+sumr;
}
void update(int node,int start,int end,int l,int r,int x)
{
if(l<=start&&r>=end)
{
tree[node].lazy+=x;
tree[node].sum+=x*tree[node].len;
return;
}
lazzy(node);
int ln=node*2+1;
int rn=node*2+2;
int mid=(start+end)>>1;
if(l<=mid)
update(ln,start,mid,l,r,x);
if(r>mid)
update(rn,mid+1,end,l,r,x);
tree[node].sum=tree[ln].sum+tree[rn].sum;
}