poj

#include<iostream>
#include<string.h>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<iomanip>
#define inf 0x3f3f3f3f
#define ios() std::ios::sync_with_stdio(false)
#define cin() cin.tie(0)
#define cout() cout.tie(0)
#define mem1(a) memset(a,0,sizeof(a))
#define mem2(b) memset(b,'\0',sizeof(b))
typedef long long ll;
using namespace std;

//10 5
//1 2 3 4 5 6 7 8 9 10 //十個數
//Q 4 4 ->4//查詢操作:查詢區間[4,4]內所有和
//Q 1 10 ->55
//Q 2 4 ->9
//C 3 6 3 //插入操作:對[3,6]中每一個數+3
//Q 2 4 ->15

// [1,10]
// / \
// [1,5] [6,10]
// / \ / \
// [1,3] [4,5] [6,8] [9,10]
// / \ / \ / \ / \
// [1,2] 3 4 5 [6,7] 8 9 10
// / \ / \
// 1 2 6 7
ll sum[400020],lazy[400020];

void build(int left,int right,int point)
//傳入左區間、右區間、根節點
{
if(left==right)
{
cin>>sum[point];
return;
}
int mid=(left+right)/2;//>>1
build(left,mid,point<<1);//point<<1//先建立左節點
build(mid+1,right,point<<1|1);//建立右節點,節點數+1
//|位運算,先把a,b轉化成二進制,然后位相或,有1出1,無1出0,比直接+1運算快
sum[point]=sum[point<<1]+sum[point<<1|1];//左右節點相加
}

void pushdown(int point,int len)
{
if(lazy[point])//表示有過懶惰標記,進行下面的push將其他下面的節點進行更新
{
lazy[point<<1]+=lazy[point];
lazy[point<<1|1]+=lazy[point];
sum[point<<1]+=lazy[point]*(len-(len>>1));
sum[point<<1|1]+=lazy[point]*(len>>1);
lazy[point]=0;//用完后取消標記
}
}

//left,r,1,n,1,up)
void update(int x,int y,int left,int right,int point,int up)
{
if(x<=left&&y>=right)
{
sum[point]+=up*(right-left+1);
lazy[point]+=up;//lazy標記改變量
return;
}
pushdown(point,right-left+1);
int mid=(left+right)/2;
if(x<=mid)
update(x,y,left,mid,point<<1,up);
if(y>mid)
update(x,y,mid+1,right,point<<1|1,up);
sum[point]=sum[point<<1]+sum[point<<1|1];
}

//left,r,1,n,1
ll query(int x,int y,int left,int r,int point)
{
//x,y是題目給定需要求的區間
//left和r是題目原有區間
if(x<=left&&y>=r)//和區間沒有交集
return sum[point];
pushdown(point,r-left+1);
int mid=(left+r)/2;
ll sum=0;
if(x<=mid)
sum=query(x,y,1,mid,point<<1);
if(y>mid)
sum+=query(x,y,mid+1,r,point<<1|1);
return sum;
}
int main()
{
ios();
cin();
cout();
int n,m;
while(cin>>n>>m)
{
mem1(sum);
mem2(lazy);
build(1,n,1);//開始建樹
//傳入左區間、右區間、根節點
while(m--)
{
string ss;
int left,r,up;
cin>>ss;
if(ss[0]=='Q')
{
cin>>left>>r;
cout<<query(left,r,1,n,1)<<endl;;
}

else if(ss[0]=='C')
{
cin>>left>>r>>up;//up是插入的數字量
update(left,r,1,n,1,up);
}
}
}
return 0;
}