二更——

有神仙反映數(shù)星星那個(gè)題外鏈炸了，我決定把圖給你們粘一下，漢語(yǔ)翻譯的話在一本通提高篇的樹狀數(shù)組那一章里有，同時(shí)也修改了一些漢語(yǔ)語(yǔ)法的錯(cuò)誤

?

這段時(shí)間學(xué)了線段樹組，當(dāng)神仙們都在學(xué)kmp和hash的時(shí)候，我這個(gè)蒟蒻致遠(yuǎn)星了，，，，，所以在補(bǔ)完字符串算法之后我決定再補(bǔ)一補(bǔ)數(shù)據(jù)結(jié)構(gòu)

這篇總結(jié)主要就是給自己看的，所以樹狀數(shù)組的原理請(qǐng)移步這篇

高赫奆佬的blogs

這篇以例題為主

首先是一道板子題

P3374 【模板】樹狀數(shù)組 1

這個(gè)題是個(gè)板子

讓我們來(lái)看一看樹狀數(shù)組的一些操作

1.對(duì)某一個(gè)點(diǎn)添加某個(gè)值

void update(int x,int y)
{while(x <= n){t[x] += y;x += lowbit(x);}
}

考慮樹狀數(shù)組t[ x] 表示區(qū)間[x-lowbit(x)+1,x]之間所有數(shù)的和，又因?yàn)樗衳為2的整倍數(shù)的t數(shù)組的值都來(lái)自于前面2的整倍數(shù)的貢獻(xiàn)，所以我們要把每一個(gè)lowbit（x）都進(jìn)行添加x值

如果你看不懂，可以看看這個(gè)圖

2.還有就是查詢某個(gè)區(qū)間的值

我們肯定知道在前綴和中[x,y]這個(gè)區(qū)間的值就是sum(y)-sum(x-1)對(duì)吧，然后我們只需要寫出來(lái)sum函數(shù)就可以了

int sum(int x)
{int res = 0;while(x>0){res += t[x];x -= lowbit(x);}return res;
}

還有就是快速求lowbit（x）的值的代碼

int lowbit(int x)
{return x & (-x);
}

這樣我們這道板子題就差不多完事了

放一下代碼吧

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, t[500010];
int lowbit(int x)
{return x & (-x);
}
void update(int x,int y)
{while(x <= n){t[x] += y;x += lowbit(x);}
}
int sum(int x)
{int res = 0;while(x>0){res += t[x];x -= lowbit(x);}return res;
}
int main()
{scanf("%d%d", &n, &m);for (int i = 1, v; i <= n; ++i){scanf("%d", &v);update(i,v);}for (int i = 1, temp, u, v; i <= m; ++i){scanf("%d%d%d", &temp, &u, &v);if(temp == 1)    update(u,v);else    printf("%d\n",sum(v) - sum(u - 1));}return 0;
}

下面來(lái)看到第二個(gè)板子

P3368 【模板】樹狀數(shù)組 2

這個(gè)題換了一個(gè)問(wèn)法，問(wèn)的是某幾個(gè)數(shù)的差，所以我們?cè)偬砑硬罘诌@個(gè)元素

把原本p[x]表示的意思變?yōu)閇x-lowbiut(x)+1,x]這個(gè)區(qū)間右端點(diǎn)與左端點(diǎn)的差，因?yàn)檫€是按照l(shuí)owbit（x）來(lái)倍增的，所以我們能夠通過(guò)sum這個(gè)函數(shù)來(lái)求得任意兩個(gè)數(shù)的差分值，然后相減就能得到所求數(shù)字，不明白的話，我慢慢講來(lái)。

首先sum和update的方法是不變的，但是因?yàn)槲覀儗?duì)于一個(gè)區(qū)間內(nèi)的所有數(shù)都加z，所以這個(gè)區(qū)間內(nèi)的差分值是不變的，我們只對(duì)左端點(diǎn)的差分值加z，右端點(diǎn)+1的位置的差分值-z就行了

update(l,z);
update(r + 1,-z);

想要求某一個(gè)數(shù)的話，直接將這個(gè)數(shù)到1所有的差分值相加即可求得，也就是sum（x）

這個(gè)題就完事啦

#include <iostream>
#include <cstdio>
using namespace std;    
long long n, m,t[500010];
inline int lowbit(int x)
{return x & (-x);
}  
inline void update(int x,int y)
{while(x<=n){t[x] += y;x += lowbit(x);}
}
inline int sum(int x)
{int res = 0;while(x){res += t[x];x -= lowbit(x);}return res;
}
int main()
{scanf("%d%d", &n, &m);int now,past = 0;for (int  i = 1; i <= n; ++i){scanf("%d", &now);update(i,now - past);past = now;}for (int i = 1,k; i <= m;++i){scanf("%d", &k);if(k == 1){int x, y, z;scanf("%d%d%d", &x, &y, &z);update(x,z);update(y + 1,-z);}else{int x;scanf("%d", &x);printf("%d\n", sum(x));}}return 0;
}

還有一道比較好玩的題目

ural 1028 stars

?

這個(gè)題的大體意思就是給你星星的坐標(biāo)，在星星左下方的（包括正左和正下）的星星有k顆，那么這個(gè)星星就是k級(jí)的，問(wèn)每一級(jí)星星的數(shù)量，星星的坐標(biāo)按照y軸升序輸入，y軸相同的按x軸升序輸入

?

怎么說(shuō)呢，一看到坐標(biāo)肯定先想到二維數(shù)組，但是數(shù)據(jù)范圍在這個(gè)地方了，你肯定是不能開p[15000][15000]的，我們?cè)倏纯催@個(gè)題，他的輸入很棒啊，保證了后輸入的一定是把之前輸入的星星包含在內(nèi)了，所以我們就可以用a[x] 表示橫坐標(biāo)為x的星星的個(gè)數(shù)，然后跑一遍統(tǒng)計(jì)一下就可以辣

上代碼

這地方有個(gè)坑，就是星星的坐標(biāo)可以是(0,0)但是我們跑前綴和的時(shí)候因?yàn)橛衛(wèi)owbit（x）操作，下標(biāo)必須從1開始，所以我們把每一個(gè)讀進(jìn)來(lái)的x都++，這樣的話不僅不影響最終結(jié)果，而且也不會(huì)出鍋啦

#include <stdio.h>
#include <stdlib.h>
#include <string.h>using namespace std;int c[32010];
int level[32010];//求2的K次冪
int lowbit(int t)
{return t&(-t);
}
//更新樹狀數(shù)組
void update(int t)
{while(t<32010){++c[t];t+=lowbit(t);}
}
//獲取前N項(xiàng)和
int getSum(int t)
{int sum = 0;while(t>0){sum+=c[t];t-=lowbit(t);}return sum;
}
int main()
{int n;int x;int y;int i;int sum;scanf("%d",&n);memset(c,0,sizeof(c));memset(level,0,sizeof(c));for(i = 0;i<n;i++){scanf("%d%d",&x,&y);++x;//星星的左邊可以從0開始，但是update函數(shù)的參數(shù)卻不能是0，所有向后移一位
        update(x);sum = getSum(x);++level[sum];}for(i = 0;i<n;i++){printf("%d\n",level[i+1]);}return 0;
}

ok 完事~

轉(zhuǎn)載于:https://www.cnblogs.com/this-is-M/p/11082874.html

總結(jié)

以上是生活随笔為你收集整理的树状数组的理解（前缀和 and 差分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。