题意：Q是询问区间和，C是在区间内每个节点加上一个值
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 <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <queue>
# define LL long long
using namespace std ; const int maxn = ; LL sum[maxn<<] ; //结点开4倍
LL add[maxn<<] ; //延迟标记 void PushUP(int rt) //更新到父节点
{
sum[rt] = sum[rt * ] + sum[rt * + ] ; //rt 为当前结点
} void PushDown(int rt , int m ) //向下更新
{
if (add[rt])
{
add[rt * ] += add[rt] ;
add[rt * + ] += add[rt] ;
sum[rt * ] += (m - m / ) * add[rt] ;
sum[rt * + ] += (m / ) * add[rt] ;
add[rt] = ;
}
} void build(int l , int r , int rt) //构建线段树
{
add[rt] = ;
if (l == r)
{
cin>>sum[rt];
return ;
}
int m = (l + r) / ;
build(l , m , rt * ) ;
build(m + , r , rt * +) ;
PushUP(rt) ;
} void updata(int L , int R , int c , int l , int r , int rt) //成段增减
{
if (L <= l && r <= R)
{
add[rt] += c ;
sum[rt] += (r - l + ) * c ;
return ;
}
PushDown(rt , r - l + ) ;
int m = (l + r) / ; if (L <= m)
updata(L , R , c , l , m , rt * ) ;
if (R > m)
updata(L , R , c , m + , r , rt * + ) ;
PushUP(rt) ;
} LL query(int L , int R , int l , int r , int rt) //区间求和
{
if (L <= l && r <= R)
return sum[rt] ;
PushDown(rt , r - l + ) ;
int m = (l + r) / ;
LL ret = ;
if (L <= m)
ret += query(L , R , l , m , rt * ) ;
if (R > m)
ret += query(L , R , m + , r , rt * + ) ;
return ret ;
} int main ()
{
//freopen("in.txt","r",stdin) ;
int n , m ;
scanf("%d %d" , &n , &m) ; build( , n , ) ;
while(m--)
{
char op[] ;
int a , b , c ;
scanf("%s" , op) ;
if(op[] == 'Q')
{
scanf("%d %d" , &a , &b) ;
cout<<query(a , b , , n , )<<endl ;
}
else
{
scanf("%d %d %d" , &a , &b , &c) ;
updata(a , b , c , , n , ) ;
}
} return ;
}