#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <string> #include <vector> #include <list> #include <map> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <numeric> #include <functional> using namespace std; #define LL __int64 #define DB double #define N 100500 const int INF = 0x3f3f3f3f; const LL INFF = 1LL << 60; const DB EPS = 1e-9; const DB OO = 1e15; const DB PI = acos(-1.0); LL sum[N*4],col[N*4],ql,qr,v; char s[3]; void Pushup(LL rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(LL rt,LL l,LL r) { col[rt] = 0; if(l == r) {scanf("%I64d",&sum[rt]);return ;} LL m = (l+r)>>1; build(rt<<1,l,m); build(rt<<1|1,m+1,r); Pushup(rt); return ; } void Pushdown(LL rt,LL m) { if(col[rt]) { col[rt<<1] += col[rt]; col[rt<<1|1] += col[rt]; sum[rt<<1] += (m-(m>>1))*col[rt]; sum[rt<<1|1] += (m>>1)*col[rt]; col[rt] = 0; return ; } } void updata(LL rt,LL l,LL r) { if(l>=ql&&r<=qr) { sum[rt] += (r-l+1)*v; col[rt] += v; return ; } Pushdown(rt,r-l+1); LL m = (l+r)>>1; if(ql<=m) updata(rt<<1,l,m); if(m<qr) updata(rt<<1|1,m+1,r); Pushup(rt); } LL Query(LL rt,LL l,LL r) { LL ans = 0 ,m; if(ql<=l&&r<=qr) return sum[rt]; Pushdown(rt,r-l+1); m = (l+r)>>1; if(ql<=m) ans+=Query(rt<<1,l,m); if(qr>m) ans+=Query(rt<<1|1,m+1,r); return ans; } int main() { LL n,m; while(~scanf("%I64d %I64d",&n,&m)) { build(1,1,n); while(m--) { scanf("%s",s); if(s[0] == 'C') { scanf("%I64d %I64d %I64d",&ql,&qr,&v); updata(1,1,n); }else { scanf("%I64d %I64d",&ql,&qr); LL ans = Query(1,1,n); printf("%I64d ",ans); } } } return 0; }
线段树区间修改