題目
需要滿足兩種操作，區間修改和區間查詢
分析（樹狀數組）
設 t r e e [ i ] = a [ i ] − a [ i − 1 ] tree[i]=a[i]-a[i-1] tree[i]=a[i]−a[i−1]（差分），那麼容易得到：
t r e e [ 1 ] + t r e e [ 2 ] + … + t r e e [ i ] = a [ i ] tree[1]+tree[2]+…+tree[i]=a[i] tree[1]+tree[2]+…+tree[i]=a[i]這個公式
是以，隻需要維護 t r e e tree tree數組就可以實作區間修改了。
如何實作區間查詢呢？
我們已經推出了一個公式：
t r e e [ 1 ] + t r e e [ 2 ] + … t r e e [ i ] = a [ i ] tree[1]+tree[2]+…tree[i]=a[i] tree[1]+tree[2]+…tree[i]=a[i]
那麼，對于1到r的區間和，即為：
a [ 1 ] + a [ 2 ] + … … + a [ r − 1 ] + a [ r ] a[1]+a[2]+……+a[r-1]+a[r] a[1]+a[2]+……+a[r−1]+a[r]
= t r e e [ 1 ] + ( t r e e [ 1 ] + t r e e [ 2 ] ) + … + ( t r e e [ 1 ] + … + t r e e [ r ] ) =tree[1]+(tree[1]+tree[2])+…+(tree[1]+…+tree[r]) =tree[1]+(tree[1]+tree[2])+…+(tree[1]+…+tree[r])
= ( t r e e [ 1 ] ∗ r ) + ( t r e e [ 2 ] ∗ r − 1 ) + … ( t r e e [ r ] ∗ 1 ) =(tree[1]*r)+(tree[2]*r-1)+…(tree[r]*1) =(tree[1]∗r)+(tree[2]∗r−1)+…(tree[r]∗1)
= r ∗ ( t r e e [ 1 ] + t r e e [ 2 ] + … + t r e e [ r ] ) − ( t r e e [ 1 ] ∗ 0 + t r e e [ 2 ] ∗ 1 + … + t r e e [ r ] ∗ ( r − 1 ) ) =r*(tree[1]+tree[2]+…+tree[r])-(tree[1]*0+tree[2]*1+…+tree[r]*(r-1)) =r∗(tree[1]+tree[2]+…+tree[r])−(tree[1]∗0+tree[2]∗1+…+tree[r]∗(r−1))
對于 a a a的樹狀數組(差分) t r e e tree tree，建立一個新的樹狀數組 t r e e 1 tree1 tree1使得： t r e e 1 [ i ] = t r e e [ i ] ∗ ( i − 1 ) tree1[i]=tree[i]*(i-1) tree1[i]=tree[i]∗(i−1)
之後，x到y的區間和即為：
( y ∗ s u m ( t r e e , y ) − ( x − 1 ) ∗ s u m ( t r e e , x − 1 ) ) − ( s u m ( t r e e 1 , y ) − s u m ( t r e e 1 , x − 1 ) ) (y*sum(tree,y)-(x-1)*sum(tree,x-1))-(sum(tree1,y)-sum(tree1,x-1)) (y∗sum(tree,y)−(x−1)∗sum(tree,x−1))−(sum(tree1,y)−sum(tree1,x−1))
代碼（樹狀數組）
#include <cstdio>
typedef long long ll;
ll n,a[100001],b[100001],m,o;
ll in(){
ll ans=0; char c=getchar(); int f=1;
while ((c<48||c>57)&&c!='-') c=getchar();
if (c=='-') f=-f,c=getchar();
while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void add(ll x,ll k){while (x<=n) a[x]+=k,x+=-x&x;}//插入
void add1(ll x,ll k){while (x<=n) b[x]+=k,x+=-x&x;}//插入
ll sum(ll x){ll ans=0; while (x) ans+=a[x],x-=-x&x; return ans;}//求和
ll sum1(ll x){ll ans=0; while (x) ans+=b[x],x-=-x&x; return ans;}//求和
void print(ll ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
int main(){
n=in(); m=in(); ll x;
for (register int i=1;i<=n;i++)
x=in(),add(i,x-o),add1(i,(i-1)*(x-o)),o=x;//初值
while (m--){
ll l,r; char c=getchar();
while (c<65||c>90) c=getchar();
if (c=='C'){
l=in(); r=in(); x=in();
add(l,x); add(r+1,-x); add1(l,x*(l-1)); add1(r+1,-x*r);//差分思想
}
else {
l=in(); r=in(); ll ans=r*sum(r)-sum1(r)-(l-1)*sum(l-1)+sum1(l-1);//字首和
if (ans<0) putchar('-'),ans=-ans;
if (ans) print(ans); else putchar('0'); putchar('\n');
}
}
return 0;
}
分析（線段樹）
當然這道題可以用線段樹去做，不過要滿足區間修改和區間查詢需要用懶标記（延遲标記）……
代碼（線段樹）
#include <cstdio>
typedef long long ll;
ll w[400001],lazy[400001],a[100001],n,m;
ll in(){
ll ans=0; char c=getchar(); int f=1;
while ((c<48||c>57)&&c!='-') c=getchar();
if (c=='-') f=-f,c=getchar();
while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void build(int k,int l,int r){//建線段樹
if (l==r) {w[k]=a[l]; return;}
int mid=(l+r)>>1;
build(k<<1,l,mid); build(k<<1|1,mid+1,r);
w[k]=w[k<<1]+w[k<<1|1];
}
void ask(int k,int l,int r,int x,int y,ll &ans){//詢問
if (l==x&&r==y) {ans+=w[k]; return;}
int mid=(l+r)>>1;
if (lazy[k]){//懶标記
w[k<<1]+=lazy[k]*(mid-l+1);
w[k<<1|1]+=lazy[k]*(r-mid);
lazy[k<<1]+=lazy[k];
lazy[k<<1|1]+=lazy[k];
lazy[k]=0;
}
if (y<=mid) ask(k<<1,l,mid,x,y,ans);
else if (x>mid) ask(k<<1|1,mid+1,r,x,y,ans);
else ask(k<<1,l,mid,x,mid,ans),ask(k<<1|1,mid+1,r,mid+1,y,ans);
}
void update(int k,int l,int r,int x,int y,int t){//更新
if (l==x&&r==y) {w[k]+=t*(r-l+1); lazy[k]+=t; return;}
int mid=(l+r)>>1;
if (lazy[k]){
w[k<<1]+=lazy[k]*(mid-l+1);
w[k<<1|1]+=lazy[k]*(r-mid);
lazy[k<<1]+=lazy[k];
lazy[k<<1|1]+=lazy[k];
lazy[k]=0;
}
if (y<=mid) update(k<<1,l,mid,x,y,t);
else if (x>mid) update(k<<1|1,mid+1,r,x,y,t);
else update(k<<1,l,mid,x,mid,t),update(k<<1|1,mid+1,r,mid+1,y,t);
w[k]=w[k<<1]+w[k<<1|1];
}
void print(ll ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
int main(){
n=in(); m=in();
for (int i=1;i<=n;i++) a[i]=in();
build(1,1,n);
while (m--){
char c=getchar(); while (c<65||c>90) c=getchar();
int l=in(); int r=in();
if (c=='C') update(1,1,n,l,r,in());
else {
ll ans=0; ask(1,1,n,l,r,ans);
if (ans<0) putchar('-'),ans=-ans;
if (ans) print(ans); else putchar('0'); putchar('\n');
}
}
return 0;
}
分析(分塊)
然而可以用一種時間較長但是碼長短又直覺的方法解決這個問題，那就是分塊，采取大段維護，小段樸素的方法，時間複雜度 O ( ( n + q ) l o g n ) O((n+q)logn) O((n+q)logn)（因為超直覺，就不解釋了）
代碼(分塊)
#include <cstdio>
#include <cmath>
typedef long long ll;
ll sum[100001],add[100001],a[100001];
int l[321],r[321],n,m,t,pos[100001];
ll in(){
ll ans=0; char c=getchar(); int f=1;
while ((c<48||c>57)&&c!='-') c=getchar();
if (c=='-') f=-f,c=getchar();
while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void print(ll ans){if (ans>9) print(ans/10); putchar(ans%10+48);}
void update(int x,int y,int d){
int p=pos[x],q=pos[y];
if (p==q){
for (register int i=x;i<=y;i++) a[i]+=d;
sum[p]+=d*(y-x+1);
}
else{
for (register int i=p+1;i<=q-1;i++) add[i]+=d;
for (register int i=x;i<=r[p];i++) a[i]+=d;
sum[p]+=d*(r[p]-x+1);
for (register int i=l[q];i<=y;i++) a[i]+=d;
sum[q]+=d*(y-l[q]+1);
}
}
ll ask(int x,int y){
int p=pos[x],q=pos[y];
ll ans=0;
if (p==q){
for (register int i=x;i<=y;i++) ans+=a[i];
ans+=add[p]*(y-x+1);
}
else {
for (register int i=p+1;i<=q-1;i++) ans+=sum[i]+add[i]*(r[i]-l[i]+1);
for (register int i=x;i<=r[p];i++) ans+=a[i];
ans+=add[p]*(r[p]-x+1);
for (register int i=l[q];i<=y;i++) ans+=a[i];
ans+=add[q]*(y-l[q]+1);
}
return ans;
}
int main(){
n=in(); m=in(); int t=sqrt(n);
for (register int i=1;i<=n;i++) a[i]=in();
for (register int i=1;i<=t;i++) l[i]=(i-1)*t+1,r[i]=i*t;
if (r[t]<n) t++,l[t]=r[t-1]+1,r[t]=n;
for (register int i=1;i<=t;i++)
for (register int j=l[i];j<=r[i];j++) pos[j]=i,sum[i]+=a[j];
while (m--){
char c=getchar(); while (c<65||c>90) c=getchar();
int x=in(); int y=in();
if (c=='C') update(x,y,in());
else {
ll ans=ask(x,y);
if (ans<0) putchar('-'),ans=-ans;
if (ans) print(ans); else putchar('0'); putchar('\n');
}
}
return 0;
}