//每天整理一点，太多了
https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712（ORZ）
POJ 3468 板子题 注意下数据范围 （因为int会爆，以后一定好好看题，浪费我10min....）
http://poj.org/problem?id=3468
#include<iostream>//线段树题目集
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 4e5 + 15;
typedef long long ll;
typedef struct
{
ll l,r,sum,f;//sum为区间和,f为懒人标记
}node;
node Tree[maxn];//线段树
ll n,q;
ll _left,_right,value;
void buildTree(int l,int r,int cur)
{
Tree[cur].l = l;
Tree[cur].r = r;//左右区间范围
if(l==r)
{
scanf("%lld",&Tree[cur].sum);
return;
}
int mid = (l + r) >> 1;
buildTree(l,mid,cur*2);
buildTree(mid+1,r,cur<<1|1);
Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;
}//建树
void Down(int cur)
{
Tree[2*cur].f += Tree[cur].f;
Tree[2*cur+1].f += Tree[cur].f;
Tree[2*cur].sum += (Tree[2*cur].r - Tree[2*cur].l + 1)*Tree[cur].f;
Tree[2*cur+1].sum += (Tree[2*cur+1].r - Tree[2*cur+1].l + 1)*Tree[cur].f;
Tree[cur].f = 0;//因为已经传下去了,所以清零
}//懒标记下传
ll ans;
void ask_interval(int cur)
{
if(_left<=Tree[cur].l&&Tree[cur].r<=_right)
{
ans += Tree[cur].sum;
return;
}
if(Tree[cur].f)
Down(cur);//下传懒人标记
ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
if(_left<=mid)
ask_interval(cur<<1);
if(_right>mid)
ask_interval(cur<<1|1);
}
void change_interval(int cur)
{
if(_left<=Tree[cur].l&&Tree[cur].r<=_right)//if node 在区间范围内
{
Tree[cur].sum += (Tree[cur].r - Tree[cur].l + 1)*value;
Tree[cur].f += value;
return;
}
if(Tree[cur].f)
Down(cur);
ll mid = (Tree[cur].l + Tree[cur].r) >> 1;//mid 中间值
if(_left<=mid)
change_interval(cur<<1);
if(_right>mid)
change_interval(cur<<1|1);
Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;//(important) 更新完后一定要更新sum的总和值
}//线段树区间修改
int main()
{
while(scanf("%lld%lld",&n,&q)==2)//写返回值,不然可能会有些很SB的output 超出limit
{
memset(Tree,0,sizeof(Tree));
buildTree(1,n,1);//1 ~ n为范围,cur 为当前节点
char cmd;
while(q--)
{
ans = 0;
getchar();
scanf("%c",&cmd);//区间查询,区间修改
scanf("%lld%lld",&_left,&_right);
if(cmd=='Q')
{
ask_interval(1);
cout<<ans<<endl;
}else{
scanf("%lld",&value);
change_interval(1);
}
}
}
}