前言
樹(shù)狀數(shù)組
先導(dǎo)
單點(diǎn)修改區(qū)間查詢
區(qū)間修改區(qū)間查詢
線段樹(shù)
先導(dǎo)
單點(diǎn)修改區(qū)間查詢--遞歸形式
單點(diǎn)修改區(qū)間查詢--非遞歸形式
區(qū)間修改區(qū)間查詢--遞歸形式
區(qū)間修改區(qū)間查詢--非遞歸形式
補(bǔ)充
前言看了三天樹(shù)，腦袋要爛掉了，我是從線段樹(shù)開(kāi)始學(xué)的然后再回頭看的樹(shù)狀數(shù)組，找到了一些怪方法（師哥們沒(méi)見(jiàn)過(guò)的useless方法），我盡量講清楚一些，重點(diǎn)寫(xiě)自己理解得慢的地方。一下子看不懂很正常，感覺(jué)這個(gè)東西是需要時(shí)間理解，我第一天見(jiàn)他傻在那了，但是過(guò)了三天再看看覺(jué)得其實(shí)也挺好理解的（所以這幾天我都學(xué)了什么效率好低啊?。?/p>樹(shù)狀數(shù)組 先導(dǎo)
首先我們了解一下樹(shù)狀數(shù)組是個(gè)什么東西。
（這個(gè)圖非常非常非常棒，后面不懂了就對(duì)著圖看！）
a數(shù)組是我們的原數(shù)組，我們開(kāi)個(gè)t數(shù)組（在下面的代碼里sum數(shù)組為t）把a(bǔ)變成一個(gè)樹(shù)的形式，這樣在求和的時(shí)候就可以減少循環(huán)的次數(shù)，從而優(yōu)化時(shí)間。這個(gè)樹(shù)的構(gòu)造原理就是按照二進(jìn)制數(shù)字尾部0的個(gè)數(shù)分層，這樣會(huì)更好算，至于怎么算，這里引入一個(gè)lowbit函數(shù)。很明顯可以看出來(lái)這個(gè)算術(shù)方法是取反+1按位與。
重慶分公司
重慶分公司
ll lowbit(ll x) {
return x & (-x);
}對(duì)不起我講不清楚，放個(gè)師哥的博客大家自己看吧淺談lowbit運(yùn)算_劭兮劭兮的博客-博客?????
我主要說(shuō)一說(shuō)lowbit函數(shù)求出來(lái)的是什么：根據(jù)定義我們知道這個(gè)求的是一個(gè)數(shù)的尾部第一個(gè)1及后面的0組成的十進(jìn)制數(shù)，但這太抽象了；我們觀察一下可以發(fā)現(xiàn)，這個(gè)東西求出來(lái)的是一個(gè)數(shù)與他右上節(jié)點(diǎn)（即父節(jié)點(diǎn)）之間的距離。我們看圖還可以發(fā)現(xiàn)，如果這個(gè)數(shù)是奇數(shù)，那他的直接父節(jié)點(diǎn)就是比他大的最小偶數(shù)，如果是偶數(shù)，那父節(jié)點(diǎn)就是比他大的最小2^n。（這個(gè)發(fā)現(xiàn)沒(méi)什么用）
單點(diǎn)修改區(qū)間查詢#includeusing namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int n, q;
int arr[N];
ll sum[N];
ll lowbit(ll x) {
return x & (-x);
}
void build() {
for (int i = 1; i<= n; ++i) {
sum[i] += arr[i];
ll fa = i + lowbit(i);
if (fa<= n)
sum[fa] += sum[i];
}
}//O(n)建樹(shù) *1
void add(int p, int w) {
//arr[p] += w;//可改可不改
for (int i = p; i<= n; i += lowbit(i)) {
sum[i] += w;
}
}//單點(diǎn)修改 *2
ll ask(int x) {
ll ans = 0;
for (int i = x; i >0; i -= lowbit(i)) {//注意別錯(cuò)
ans += sum[i];
}
return ans;
}//單點(diǎn)查詢
void search(int l, int r) {
ll ans = ask(r) - ask(l - 1);
printf("%lld\n", ans);
return;
}//區(qū)間查詢 *3
int main() {
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
scanf("%d %d", &n, &q);
memset(sum, 0, sizeof sum);
for (int i = 1; i<= n; ++i) {
scanf("%d", &arr[i]);
}
build();
while (q--) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
switch (a) {
case 1:
search(b, c);
break;
case 2:
add(b, c);
break;
}
}
return 0;
} *1：我的建樹(shù)方法跟師哥們不一樣，師哥們沒(méi)建樹(shù)，直接輸入一個(gè)元素就把他加進(jìn)樹(shù)里，我沒(méi)懂他們?cè)趺锤傻?，但是這樣建樹(shù)時(shí)間也是O(n)，因?yàn)槲覀冎槐闅v了一遍，從小往大捋，把每一個(gè)數(shù)都加到他直接父節(jié)點(diǎn)里，這樣可以保證遍歷到某個(gè)數(shù)時(shí)，他的子節(jié)點(diǎn)一定被加完了，不重不漏。（不懂就返回去看圖手推）
*2：在先導(dǎo)里提到，lowbit函數(shù)求出來(lái)了他與父節(jié)點(diǎn)的距離，那加上他就直接讓他變成了他爸爸，相當(dāng)于我們找到葉節(jié)點(diǎn)，逐層遞加直到某個(gè)節(jié)點(diǎn)沒(méi)有爸爸。單點(diǎn)查詢同理。
*3：l ->r ==? ( 1 ->r ) - ( 1 ->l )
區(qū)間修改區(qū)間查詢默認(rèn)大家都會(huì)差分了我不細(xì)說(shuō)了。?
同樣地，我們構(gòu)造一個(gè)差分?jǐn)?shù)組使每次修改在差分?jǐn)?shù)組上操作，下面展示根據(jù)差分?jǐn)?shù)組逆推ans：
看不懂沒(méi)關(guān)系，這里有另一種形式：
ans=a[1]+a[2]+……+a[r-1]+a[r]?
=tree[1]+(tree[1]+tree[2])+……+(tree[1]+……+tree[r])?
=(tree[1]*(r))+(tree[2]*(r-1))+……(tree[r]*1)
=r*(tree[1]+tree[2]+……+tree[r]) - (tree[1]*0+tree[2]*1+……+tree[r]*(r-1))
=? ?
= 上圖的式子
那么我們就需要構(gòu)造兩個(gè)差分?jǐn)?shù)組來(lái)維護(hù)區(qū)間和。?
#includeusing namespace std;
const int N = 1e6 + 5;
typedef long long ll;
ll n, q;
ll arr[N];//原數(shù)組
ll tree1[N], tree2[N];//差分?jǐn)?shù)組1，2
//tree1=bi
//tree2=bi*(i-1)
ll lowbit(ll x) {
return x & (-x);
}
void add1(ll a, ll b) {
for (ll i = a; i<= n; i += lowbit(i)) {
tree1[i] += b;
}
}//加tree1
void add2(ll a, ll b) {
for (ll i = a; i<= n; i += lowbit(i)) {
tree2[i] += b;
}
}//加tree2
ll ask1(ll x) {
ll ans = 0;
for (ll i = x; i >0; i -= lowbit(i)) {
ans += tree1[i];
}
return ans;
}
ll ask2(ll x) {
ll ans = 0;
for (ll i = x; i >0; i -= lowbit(i)) {
ans += tree2[i];
}
return ans;
}
//單點(diǎn)查詢
ll solve(ll x) {
return (x) * ask1(x) - ask2(x);
}//1 ->x區(qū)間查詢
void search(ll l, ll r) {
ll ans = 0;
ans = solve(r) - solve(l - 1);
printf("%lld\n", ans);
}//區(qū)間查詢
int main() {
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//這個(gè)是解綁cin cout
scanf("%lld %lld", &n, &q);
for (ll i = 1; i<= n; ++i) {
scanf("%lld", &arr[i]);
add1(i, arr[i] - arr[i - 1]);
add2(i, (arr[i] - arr[i - 1]) * (i - 1));
//tree2[i]=tree1[i]*(i-1)
}
while (q--) {
ll a, b, c, d;
scanf("%lld", &a);
switch (a) {
case 1:
scanf("%lld %lld", &b, &c);
search(b, c);
break;
case 2:
scanf("%lld %lld %lld", &b, &c, &d);
add1(b, d);
add1(c + 1, -d);
add2(b, d * (b - 1));
add2(c + 1, -d * c);
break;
}
}
return 0;
} 樹(shù)狀數(shù)組就差不多到這里辣，其實(shí)還有二維數(shù)組但我肝不動(dòng)了，過(guò)段時(shí)間再說(shuō)吧。
線段樹(shù) 先導(dǎo)來(lái)看看線段樹(shù)是個(gè)什么東西。
（ 紅色字為原數(shù)組下標(biāo)；黑色字為線段樹(shù)存儲(chǔ)下標(biāo)；紅色區(qū)間為該下標(biāo)存儲(chǔ)的內(nèi)容。）
我們注意到，線段樹(shù)是一種二叉樹(shù)，不同于樹(shù)狀數(shù)組，線段樹(shù)越往葉節(jié)點(diǎn)延伸，下標(biāo)就越大。我們對(duì)線段樹(shù)下標(biāo)的記法為：某個(gè)點(diǎn)的左兒子下標(biāo)是其下標(biāo)*2，右兒子下標(biāo)是其下標(biāo)*2+1，于是我們發(fā)現(xiàn)，左兒子必為偶數(shù)，右兒子必為奇數(shù)，反之亦然。這樣就可滿足圖中的樹(shù)形結(jié)構(gòu)。那我們的數(shù)組該開(kāi)多大呢？
嚴(yán)格來(lái)講，實(shí)際上足夠大的空間應(yīng)為n向上擴(kuò)充到大于等于n的最小2^k再*2；但是為了簡(jiǎn)便，我們可以直接記為4n。
單點(diǎn)修改區(qū)間查詢--遞歸形式#includeusing namespace std;
#define int long long//一般#define int long long
const int N = 1e5 + 5;
typedef long long ll;//多用這個(gè)
int arr[N];
ll sum[4 * N];
void updat(int x) {
sum[x] = sum[x * 2] + sum[x * 2 + 1];
}//更新
void build(int p, int l, int r) {
if (l == r) {
sum[p] = arr[l];//說(shuō)明到了葉節(jié)點(diǎn)
return;
} else {
int mid = (l + r) / 2;
build(p * 2, l, mid);//建左兒子
build(p * 2 + 1, mid + 1, r);//右兒子
}
updat(p);//每次建一個(gè)點(diǎn)就要更新他的父節(jié)點(diǎn)
}//建樹(shù)
void change(int p, int w, int l, int r, int k) {
//arr[p]+=w;當(dāng)前操作區(qū)間為（l,r);當(dāng)前點(diǎn)為k
if (l == r) {
//找到了p
sum[k] += w;
return;
} else {
//二分，其實(shí)就是分別找他的左右兒子
int mid = (l + r) / 2;
if (p<= mid)
change(p, w, l, mid, k * 2);
else
change(p, w, mid + 1, r, k * 2 + 1);
updat(k);
//理解遞歸，在我們已完成遞歸操作后，說(shuō)明已更新葉節(jié)點(diǎn)，此時(shí)應(yīng)該逐層更新其父節(jié)點(diǎn)
}
}
int search(int L, int R, int l, int r, int k) {
//目標(biāo)區(qū)間為（L,R）;當(dāng)前操作區(qū)間為（l,r);當(dāng)前點(diǎn)為k
if (L<= l && R >= r)//當(dāng)當(dāng)前區(qū)間嚴(yán)格屬于目標(biāo)區(qū)間時(shí)，返回當(dāng)前區(qū)間的值
return sum[k];
else {
int ans = 0;
int mid = (l + r) / 2;
//純純二分
if (L<= mid)
ans += search(L, R, l, mid, k * 2);
if (R >mid)
ans += search(L, R, mid + 1, r, k * 2 + 1);
return ans;
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//解綁
int n, q;
cin >>n >>q;
for (int i = 1; i<= n; ++i) {
cin >>arr[i];
}
build(1, 1, n);
while (q--) {
int a, b, c;
cin >>a >>b >>c;
switch (a) {
case 1:
cout<< search(b, c, 1, n, 1)<< '\n';
break;
case 2:
change(b, c, 1, n, 1);
break;
}
}
return 0;
} (其實(shí)會(huì)遞歸就差不多夠了，他倆時(shí)間復(fù)雜度是一樣的）
參考博客線段樹(shù)詳解 （原理，實(shí)現(xiàn)與應(yīng)用）_巖之痕的博客-博客_線段樹(shù)?
（揪了人家博客里的圖， 但我們的實(shí)現(xiàn)方法略有不同，建議看看他寫(xiě)的，講的很細(xì)很棒！）
求下標(biāo)：回看先導(dǎo)中的圖，我們觀察到原數(shù)組下標(biāo)和線段樹(shù)存儲(chǔ)下標(biāo)的差值是一定的，這個(gè)差值是什么呢？其實(shí)就是我們計(jì)算出來(lái)的2^k-1，這里減不減1無(wú)所謂，下面會(huì)提到。這個(gè)意思也就是說(shuō)，左下角為N（N=2^k）的二叉樹(shù)，可以存N個(gè)元素，其中[1..N-1]是非葉節(jié)點(diǎn),[N..2N-1]是葉節(jié)點(diǎn)。
找規(guī)律：假設(shè)我們要求[3,11]，那么其實(shí)要求的是上圖中紫圈的數(shù)，而藍(lán)圈緊緊包圍了紫圈，我們可以把區(qū)間轉(zhuǎn)換為追蹤兩條藍(lán)色鏈，上述博客講的很清晰，不再贅述，我重點(diǎn)說(shuō)我的優(yōu)化。（雙鏈匯集就是一個(gè)塔狀的東西，下面會(huì)提到。）
優(yōu)化：在他的博客里提到，如果我們要選取[1,5]區(qū)間就無(wú)法正確實(shí)現(xiàn)，所以要進(jìn)行區(qū)間擴(kuò)充，讓線段樹(shù)的下標(biāo)從0起記，讓n個(gè)元素轉(zhuǎn)變?yōu)閚+2個(gè)元素，其中頭尾為0。
但如果我們追蹤的不是藍(lán)色鏈而是紫色鏈呢？令s=左端點(diǎn)，t=右端點(diǎn)，當(dāng)s是左兒子時(shí)，其兄弟（他爸爸的右兒子）必在目標(biāo)區(qū)間內(nèi)，于是我們可以直接向上追蹤他的父親，t是右兒子時(shí)同理；當(dāng)s是右兒子時(shí)，其兄弟必不在目標(biāo)區(qū)間內(nèi)，所以我們可以加上他，由于他是目標(biāo)區(qū)間左邊界，除去他之后，左邊界就可以右移，直接讓他成為他右邊緊鄰的兄弟，此時(shí)他必為左兒子，一定可以直接向上追蹤，t是左兒子時(shí)同理。
追蹤可以繼續(xù)的條件是什么呢？即s<=t，在s==t時(shí)，我們找到了兩鏈相交點(diǎn)，這時(shí)可保證塔尖區(qū)間加且僅加一次。（這里謝謝yxgg幫我de出了bug?。。?/p>
于是，我們?cè)賮?lái)看[1,5]區(qū)間，會(huì)發(fā)現(xiàn)這種方法可以計(jì)算！這樣就不需要進(jìn)行區(qū)間擴(kuò)充了！求下標(biāo)中是否-1的問(wèn)題也可以想象為是否進(jìn)行了區(qū)間擴(kuò)充，其實(shí)擴(kuò)不擴(kuò)都可以的，影響不大。（笑死，師哥說(shuō)這個(gè)很妙，他不知道我的初衷是看不懂原博客的位運(yùn)算）
再想一遍：s是右兒子時(shí)加，t是左兒子時(shí)加。
#includeusing namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll b = 1;//大于n的最小2^n
ll n, q;
ll arr[N];//原數(shù)組
ll sum[4 * N] = {0}; //線段樹(shù)數(shù)組
void build(ll a) {
b = 1;
while (b< a + 2) {
b *= 2;
}
for (ll i = 1; i<= a; ++i) {
sum[i + b] = arr[i];
}
for (ll i = b - 1; i >0; --i) {
sum[i] = sum[i * 2] + sum[i * 2 + 1];
}
return;
}
void Update(int p, int w) {
for (int now = p + b; now; now /= 2) {
sum[now] += w;
}
return;
}
void search(int l, int r) {
ll ans = 0;
for (int s = b + l, t = b + r; s<= t; s /= 2, t /= 2) {
if (s % 2 != 0)//s是右兒子時(shí)加
ans += sum[s++];
if (t % 2 == 0)//t是左兒子時(shí)加
ans += sum[t--];
}
printf("%lld\n", ans);
return;
}
int main() {
scanf("%d %d", &n, &q);
memset(arr, 0, sizeof arr);
arr[0] = 0;
for (int i = 1; i<= n; ++i) {
scanf("%d", &arr[i]);
}
build(n);
int a, l, r;
while (q--) {
scanf("%d %d %d", &a, &l, &r);
switch (a) {
case 1:
search(l, r);
break;
case 2:
Update(l, r);
break;
}
}
return 0;
} 不同于樹(shù)狀數(shù)組，我們對(duì)線段樹(shù)區(qū)間修改的形式不再是建立差分?jǐn)?shù)組，而是給他打上標(biāo)記，注意在非葉節(jié)點(diǎn)時(shí)，我們存儲(chǔ)的內(nèi)容是一個(gè)區(qū)間而非一個(gè)元素，所以在標(biāo)記到非葉節(jié)點(diǎn)時(shí)代表他所有的子孫都要繼續(xù)加標(biāo)記，此時(shí)標(biāo)記的含義為本節(jié)點(diǎn)已更新，子節(jié)點(diǎn)標(biāo)記待下推。?
#includeusing namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll sum[4 * N], add[4 * N]; //sum求和，add為懶惰標(biāo)記
ll arr[N], n, q; //存原數(shù)組數(shù)據(jù)下標(biāo)[1,n]
void updat(int x) {
sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
void build(ll p, ll l, ll r) {
if (l == r) {
sum[p] = arr[l];
return;
} else {
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
}
updat(p);
}
void PushDown(ll now, ll ln, ll rn) {//下推標(biāo)記
//ln,rn為左子樹(shù)，右子樹(shù)的數(shù)字?jǐn)?shù)量。
if (add[now]) {
//下推標(biāo)記
add[now * 2] += add[now];
add[now * 2 + 1] += add[now];
//修改子節(jié)點(diǎn)的sum使之與對(duì)應(yīng)的add相對(duì)應(yīng)
sum[now * 2] += add[now] * ln;
sum[now * 2 + 1] += add[now] * rn;
//清除本節(jié)點(diǎn)標(biāo)記
add[now] = 0;
}
}
void Update(ll L, ll R, ll C, ll l, ll r, ll now) { //區(qū)間修改
//目標(biāo)區(qū)間為[L,R]，當(dāng)前操作區(qū)間[l,r]，當(dāng)前節(jié)點(diǎn)為now
if (L<= l && r<= R) { //當(dāng)當(dāng)前區(qū)間嚴(yán)格屬于目標(biāo)區(qū)間
sum[now] += C * (r - l + 1); //更新數(shù)字和，向上保持正確
add[now] += C; //增加add標(biāo)記，表示本區(qū)間的sum正確，子區(qū)間的sum仍需要根據(jù)add的值來(lái)調(diào)整
return ;
}
int mid = (l + r) / 2;
PushDown(now, mid - l + 1, r - mid); //下推標(biāo)記
if (L<= mid)//這里判斷左右子樹(shù)跟[L,R]有無(wú)交集，有交集才遞歸
Update(L, R, C, l, mid, now * 2);
if (R >mid)
Update(L, R, C, mid + 1, r, now * 2 + 1);
updat(now);//更新本節(jié)點(diǎn)信息
}
ll search(ll L, ll R, ll l, ll r, ll now) {
//目標(biāo)區(qū)間為[L,R]，當(dāng)前操作區(qū)間[l,r]，當(dāng)前節(jié)點(diǎn)為now
if (L<= l && r<= R) {
//在區(qū)間內(nèi)，直接返回
return sum[now];
}
ll mid = (l + r) / 2;
//下推標(biāo)記，否則sum可能不正確
PushDown(now, mid - l + 1, r - mid);
//累計(jì)答案
ll ANS = 0;
if (L<= mid)
ANS += search(L, R, l, mid, now * 2);
if (R >mid)
ANS += search(L, R, mid + 1, r, now * 2 + 1);
return ANS;
}
int main() {
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
scanf("%lld %lld", &n, &q);
for (ll i = 1; i<= n; ++i) {
scanf("%lld", &arr[i]);
}
build(1, 1, n);
while (q--) {
ll a, b, c, d;
scanf("%lld", &a);
switch (a) {
case 1:
scanf("%lld %lld", &b, &c);
cout<< search(b, c, 1, n, 1)<< '\n';
break;
case 2:
scanf("%lld %lld %lld", &b, &c, &d);
Update(b, c, d, 1, n, 1);
break;
}
}
return 0;
} 同樣地，還是看剛剛的塔，我們無(wú)法像遞歸一樣自上而下更新所有元素，于是我們只更新塔邊元素，把更新工作放到查詢里，由于查詢也是自下而上的，所以如果查詢的區(qū)間與修改區(qū)間重合，那么查詢塔和修改塔也必有重合，這時(shí)塔邊元素相交時(shí)就會(huì)更新答案以保證正確性。
上述博客代碼在oj上還是wa的就先不放了，可能是我哪里沒(méi)考慮到。
----->2022.11.25更新，我真被自己蠢無(wú)語(yǔ)了，de了一上午bug原來(lái)是因?yàn)闆](méi)開(kāi)ll，A了，注意這是擴(kuò)充數(shù)組的形式，單點(diǎn)修改那點(diǎn)優(yōu)化放在這里好像有點(diǎn)點(diǎn)問(wèn)題……需要改改才能用。
#includeusing namespace std;
typedef long long ll;
//不開(kāi)ll見(jiàn)祖宗！?。。?const int N = 1e5 + 5;
ll sum[4 * N], add[4 * N]; //sum求和，add為懶惰標(biāo)記
ll arr[N], n, q; //存原數(shù)組數(shù)據(jù)下標(biāo)[1,n]
ll b;
void build(ll n) {
b = 1;
while (b< n + 2)
b<<= 1;
for (int i = 1; i<= n; ++i)
sum[b + i] = arr[i];
for (int i = b - 1; i >0; --i) {
sum[i] = sum[i<< 1] + sum[i<< 1 | 1];
add[i] = 0;
}
}
void Update(ll L, ll R, ll C) {
ll s, t, Ln = 0, Rn = 0, x = 1;
//Ln: s一路走來(lái)已經(jīng)包含了幾個(gè)數(shù)
//Rn: t一路走來(lái)已經(jīng)包含了幾個(gè)數(shù)
//x: 本層每個(gè)節(jié)點(diǎn)包含幾個(gè)數(shù)
for (s = b + L - 1, t = b + R + 1; s ^ t ^ 1; s >>= 1, t >>= 1, x<<= 1) {
sum[s] += C * Ln;
sum[t] += C * Rn;
//更新sum，令本節(jié)點(diǎn)的sum值加上他所有出現(xiàn)變化的子孫的變化和。
if (~s & 1)
add[s ^ 1] += C, sum[s ^ 1] += C * x, Ln += x;
if ( t & 1)
add[t ^ 1] += C, sum[t ^ 1] += C * x, Rn += x;
//處理add，標(biāo)記本節(jié)點(diǎn)，意為本節(jié)點(diǎn)sum值正確，其父值待修改。
//注意到，修改sum時(shí)需要乘改變?cè)氐膫€(gè)數(shù)，而修改add標(biāo)記時(shí)不需
//因?yàn)閍dd只代表本區(qū)間內(nèi)所有元素改變C
//這里的x很巧妙，是2^k，我們觀察二叉樹(shù)的結(jié)構(gòu)，每層的節(jié)點(diǎn)數(shù)也為2^k。
}
for (; s; s >>= 1, t >>= 1) {
sum[s] += C * Ln;
sum[t] += C * Rn;
}
//更新上層sum，從下向上推，當(dāng)?shù)剿鈺r(shí)不會(huì)再出現(xiàn)新的需要增加的元素
//所以我們只需要推到樹(shù)頂把路過(guò)的每一個(gè)節(jié)點(diǎn)（即改變量所屬集合）的sum值更新即可
}
ll Query(ll L, ll R) {
ll s, t, Ln = 0, Rn = 0, x = 1;
ll ans = 0;
for (s = b + L - 1, t = b + R + 1; s ^ t ^ 1; s >>= 1, t >>= 1, x<<= 1) {
if (add[s])
ans += add[s] * Ln;
if (add[t])
ans += add[t] * Rn;
//根據(jù)標(biāo)記更新答案，如果當(dāng)前節(jié)點(diǎn)帶標(biāo)記，說(shuō)明他是修改塔的邊界
//他的兒子們?cè)谒?nèi)（是被修改數(shù)）且不帶標(biāo)記
if (~s & 1)
ans += sum[s ^ 1], Ln += x;
if ( t & 1)
ans += sum[t ^ 1], Rn += x;
//常規(guī)求和
}
for (; s; s >>= 1, t >>= 1) {
ans += add[s] * Ln;
ans += add[t] * Rn;
}
//處理上層標(biāo)記，追蹤目標(biāo)塔的邊界是否存在其他被修改元素。
return ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
scanf("%lld %lld", &n, &q);
for (ll i = 1; i<= n; ++i) {
scanf("%lld", &arr[i]);
}
build(n);
while (q--) {
ll a, b, c, d;
scanf("%lld", &a);
switch (a) {
case 1:
scanf("%lld %lld", &b, &c);
cout<< Query(b, c)<< '\n';
break;
case 2:
scanf("%lld %lld %lld", &b, &c, &d);
Update(b, c, d);
break;
}
}
return 0;
} 1. 樹(shù)狀數(shù)組適合寫(xiě)單點(diǎn)修改的題，是線段樹(shù)的縮略版，可以用樹(shù)狀數(shù)組寫(xiě)的題一定可以用線段樹(shù)，但是反過(guò)來(lái)卻不一定。
CVyjgg的話：（qwq超神yjgg好強(qiáng)！）
Q: 一般用樹(shù)狀數(shù)組還是線段樹(shù)？
A: 看情況，樹(shù)狀數(shù)組特別適合單點(diǎn)修改，通過(guò)單點(diǎn)修改能延伸出很多有意思的操作，而線段樹(shù)就適合大型區(qū)間修改，樹(shù)狀數(shù)組寫(xiě)出來(lái)的題，線段樹(shù)都能寫(xiě)，反過(guò)來(lái)不行，一般需要維護(hù)區(qū)間的東西很多的時(shí)候用線段樹(shù)，也只能用線段樹(shù)，但是線段樹(shù)很笨重，寫(xiě)起來(lái)復(fù)雜，debug更復(fù)雜。樹(shù)狀數(shù)組對(duì)于單點(diǎn)修改寫(xiě)起來(lái)很簡(jiǎn)單，一般兩三分鐘就能寫(xiě)一顆樹(shù)狀數(shù)組，樹(shù)狀數(shù)組和差分結(jié)合可以實(shí)現(xiàn)一些稍微復(fù)雜一點(diǎn)點(diǎn)的區(qū)間維護(hù)，但是如果寫(xiě)的不熟練的話很容易出錯(cuò)。所以一般先看能不能用樹(shù)狀數(shù)組，可以簡(jiǎn)單實(shí)現(xiàn)的話就樹(shù)狀數(shù)組，不行的話就線段樹(shù)。
2. 一般需要用到這個(gè)的題都有很多輸入輸出，要注意優(yōu)化（關(guān)io或scanf或快讀）。
3. 樹(shù)狀數(shù)組大大提高了空間利用率，只用開(kāi)一倍空間就足夠了，但是線段樹(shù)需要開(kāi)4n數(shù)組，浪費(fèi)空間以保證各種操作的可執(zhí)行性。
4. 線段樹(shù)每一次操作（查詢或修改）的時(shí)間復(fù)雜度都是logn的。
5. yjgg在看我代碼的時(shí)候提到，我們一般寫(xiě)這樣
typedef long long ll;//常用
#define ll long long//不常用
#define int long long//一般這么用我去查了一下這兩個(gè)的區(qū)別但沒(méi)太看懂，大概是醬紫：
#define是C語(yǔ)言中定義的語(yǔ)法，可以在預(yù)處理時(shí)進(jìn)行單純的字符串替換，不作正確性檢查，只有在編譯已被展開(kāi)的源程序時(shí)才會(huì)發(fā)現(xiàn)可能的錯(cuò)誤并報(bào)錯(cuò)。他沒(méi)有自己的作用域，只要是之前定義過(guò)的宏就都可以用。
typedef是關(guān)鍵字，在編譯時(shí)處理會(huì)進(jìn)行類型檢查。它在自己的作用域內(nèi)給一個(gè)已經(jīng)存在的類型一個(gè)別名，但不能在一個(gè)函數(shù)定義里面使用typedef。有自己的作用域。
他倆對(duì)指針的操作也不太一樣，但我指針學(xué)的很差，想了解的可以自己去查查。
?再次感謝yxgg和yjgg的指點(diǎn)！??！?
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
