輸入樣例：
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
輸出樣例：
4
55
9
15?解析：
? ? ? ? 一般樹狀數(shù)組都是單點修改、區(qū)間查詢或者單點查詢、區(qū)間修改。這道題都是區(qū)間操作。
????????
?
? ? ? ? 1. 區(qū)間修改用數(shù)組數(shù)組維護(hù)差分?jǐn)?shù)組文章來源：http://www.zghlxwxcb.cn/news/detail-625802.html
? ? ? ? 2. 區(qū)間查詢，需要log計算兩個端點的前綴和。上圖右側(cè)，可以得出，計算前綴和需要維護(hù)差分序列和? i*b[ i ]?的差分序列。文章來源地址http://www.zghlxwxcb.cn/news/detail-625802.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,m,a[N],b[N],tr1[N],tr2[N];
int lowbit(int x){
return x&-x;
}
void add1(int x,ll k){
for(int i=x;i<=n;i+=lowbit(i)) tr1[i]+=k;
}
void add2(int x,ll k){
for(int i=x;i<=n;i+=lowbit(i)) tr2[i]+=k;
}
ll sum(int x){
ll ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=tr1[i];
ans*=x+1;
for(int i=x;i;i-=lowbit(i)) ans-=tr2[i];
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i]-a[i-1];
add1(i,b[i]);
add2(i,i*b[i]);
}
while(m--){
char op;
cin>>op;
if(op=='C'){
int l,r,d;
scanf("%lld%lld%lld",&l,&r,&d);
add1(l,d);
add1(r+1,-d);
add2(l,d*l);
add2(r+1,-d*(r+1));
}
else{
int x,y;
scanf("%lld%lld",&x,&y);
printf("%lld\n",sum(y)-sum(x-1));
}
}
return 0;
}到了這里，關(guān)于243. 一個簡單的整數(shù)問題2（樹狀數(shù)組）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【算法每日一練]-結(jié)構(gòu)優(yōu)化（保姆級教程 篇4 樹狀數(shù)組，線段樹，分塊模板篇）](https://imgs.yssmx.com/Uploads/2024/02/759135-1.jpeg)
