- 簡介
- 基本思想
- 具體原理
- 資料結構
- lowbit函數的實作
- 修改一個元素的值
- 查詢
- 例題
- 樹狀數組1
- 題目描述
- 輸入輸出格式
- 輸入格式：
- 輸出格式：
- 标程
- 樹狀數組2
- 題目描述
- 輸入輸出格式
- 輸入格式：
- 輸出格式：
- 标程
簡介
樹狀數組這個東西。。。有人說它像線段樹。。。
其實感覺兩者并沒有什麼直接聯系。。。但是都是類似于樹形操作的思想，是以經常把他倆放在一塊說。。。
稍微講講我對這個算法的見解，大家看看對不對。。。
基本思想
基本思想是這樣的：
首先來講，樹狀數組較好的利用了二進制。它的每個節點的值代表的是自己和前面一些元素的和。至于到底是前面哪些元素，這就由這個節點的下标決定。
比如下面這個圖（圖中的數字代表節點的下标）：
我們假設a[MAXN]數組用來存儲初始資料，e[MAXN]代表了樹狀數組存儲内容。
例如在上圖的樹狀數組中，e[8]号記錄了a[1]…a[8]的和，即e[4]+e[6]+e[7]+a[8]。綠色的線代表樹的節點從哪些節點求和得到。
是以根據以上性質，樹狀數組實作的功能有：
- 将一個數組轉化成樹狀數組
- 改變某一個點的值
- 詢問a[1]+a[2]+······+a[x]的值
具體原理
具體的就是二進制的原理，比較繞。。。先從資料結構開始講。。。
資料結構
看圖，這個圖是上面那個圖的所有樹狀數組節點編号變成二進制以後的樣子：
你有木有發現什麼蹊跷之處？（并木有發現）
樹狀數組的節點深度其實就是它的節點編号的二進制形式中，從右往左數第一個1出現的位置。（這誰能發現啊喂！）
比如說：
6的二進制形式中（110），從右往左數第一個1出現的位置是2
7的二進制形式中（111），從右往左數第一個1出現的位置是1
8的二進制形式中（1000），從右往左數第一個1出現的位置是4
我們定義尋找這個“數字的二進制形式中，從右往左數第一個1出現的位置”（啊啊啊這個名字好長啊啊啊啊）的函數為 lowbit(x) l o w b i t ( x ) 函數。
即：
lowbit(6)=2 l o w b i t ( 6 ) = 2
lowbit(7)=1 l o w b i t ( 7 ) = 1
lowbit(8)=4 l o w b i t ( 8 ) = 4
然後你還會發現，一個節點并不一定是代表自己前面所有元素的和。隻有滿足 2n 2 n 這樣的數才代表自己前面所有元素的和。
那麼歸納一下，就能得出結論：
設節點的編号為 x x ，那麼這個的值等于 a[x−2lowbit(x)−1+1]a[x−2lowbit(x)−1+1] 到 a[x] a [ x ] 的和。
比如說 e[6]=a[6−22−1+1]+a[6]=a[5]+a[6] e [ 6 ] = a [ 6 − 2 2 − 1 + 1 ] + a [ 6 ] = a [ 5 ] + a [ 6 ]
再比如說 e[8]=a[8−24−1+1]+a[8−24−1+2]+⋅⋅⋅+a[8]=e[4]+e[6]+e[7]+a[8] e [ 8 ] = a [ 8 − 2 4 − 1 + 1 ] + a [ 8 − 2 4 − 1 + 2 ] + · · · + a [ 8 ] = e [ 4 ] + e [ 6 ] + e [ 7 ] + a [ 8 ]
這就是樹狀數組比較神奇的地方之一。
lowbit函數的實作
這個地方用到的姿勢是我難以去證明的。。。
但是我隻能告訴你：
lowbit(x)=(−x) l o w b i t ( x ) = ( − x ) & x x
在這裡要注意：
- ‘&’符号是按位取“與”運算。比如：10111011& 0110=0010 0110 = 0010
- 負數進行按位取“與”運算的時候，是對負數的“補碼”進行的。
- 什麼是補碼？以下選自百度百科
計算機中的符号數有三種表示方法，即原碼、反碼和補碼。三種表示方法均有符号位和數值位兩部分，符号位都是用0表示“正”，用1表示“負”，而數值位，三種表示方法各不相同。
補碼具有的性質：
1、對一個整數的補碼再求補碼，等于該整數自身。
2、補碼的正零與負零表示方法相同。
求給定數值的補碼分以下兩種情況：
正數
正整數的補碼是其二進制表示，與原碼相同 。
【例】+9的補碼是00001001。
（備注：這個+9的補碼是用8位2進制來表示的，補碼表示方式很多，還有16位二進制補碼表示形式，以及32位二進制補碼表示形式,64位進制補碼表示形式等。每一種補碼表示形式都隻能表示有限的數字。）
負數
求負整數的補碼，将其對應正數二進制表示所有位取反（包括符号位，0變1，1變0）後加1。
同一個數字在不同的補碼表示形式中是不同的。比如-15的補碼，在8位二進制中是11110001，然而在16位二進制補碼表示中，就是1111111111110001。以下都使用8位2進制來表示。
【例】求-5的補碼。
-5對應正數5（00000101）→所有位取反（11111010）→加1(11111011)
是以-5的補碼是11111011。
然後嘛，補碼，按位與運算。
啊啊啊我也是真的不知道為什麼會這麼神奇啊。。。反正這樣一計算就得到“一個數的二進制形式中，從右往左數第一個1出現的位置”了。。。
比如：
lowbit(6)=00000110 l o w b i t ( 6 ) = 00000110 & 11111010=00000010=2 11111010 = 00000010 = 2
真是十分有趣。。。腦子是個好東西，真希望我有。。。修改一個元素的值
因為樹狀數組的特殊性質，我們隻需要修改所有包含這個元素的節點就行了。
那怎麼操作呢？
假設本次對 e[x] e [ x ] 進行了操作，那麼下一次就對 e[x+lowbit(x)] e [ x + l o w b i t ( x ) ] 進行操作就行了。
至少看圖是這樣沒錯。論證。。。（此處省略 101010 10 10 10 字論證過程，其實我不會233333）
好吧。。。沒有論證。。。CPP代碼上來！
void add(int x,int v) { while(x<=len) { e[x]+=v; x+=lowbit(x); } }查詢
查詢是為了得到 a[1]+a[2]+⋅⋅⋅⋅⋅⋅+a[x] a [ 1 ] + a [ 2 ] + · · · · · · + a [ x ] 的值。
同樣是看圖。。。同樣是因為一些非常特殊的性質。。。
是以。。。講一下怎麼進行一波操作。。。我的能力無法證明它。。。
對于目标 x x 。。。
每一次操作：
答案加上xx對應節點的值，然後将 x x 減去它的lowbitlowbit，繼續進行這樣的操作，直到 x x 小于等于00。
int query(int x) { int sum=; while(x>) { sum+=e[x]; x-=lowbit(x); } return sum; }例題
樹狀數組1
洛谷-P3374【模闆】樹狀數組1題目描述
如題，已知一個數列，你需要進行下面兩種操作：
1.将某一個數加上x
2.求出某區間每一個數的和
輸入輸出格式
輸入格式：
第一行包含兩個整數N、M，分别表示該數列數字的個數和操作的總個數。
第二行包含N個用空格分隔的整數，其中第i個數字表示數列第i項的初始值。
接下來M行每行包含3或4個整數，表示一個操作，具體如下：
操作1： 格式：1 x k 含義：将第x個數加上k
操作2： 格式：2 x y 含義：輸出區間[x,y]内每個數的和
輸出格式：
輸出包含若幹行整數，即為所有操作2的結果。标程
貼上我的标程。。。
其實也就是完整的樹狀數組。。。
#define MAXN 500005 class TA { private: int e[MAXN]; int len; int lb(int k) { return k&(-k); } public: void add(int x,int v) { while(x<=len) { e[x]+=v; x+=lb(x); } } void init(int* getin,int _len) { len=_len; for(int i=;i<=len;i++) { add(i,*(getin+i-)); } } int query(int x) { int sum=; while(x>) { sum+=e[x]; x-=lb(x); } return sum; } }; TA ta; int a[MAXN],n,m; int main() { scanf("%d%d",&n,&m); for(int i=;i<=n;i++) { scanf("%d",&a[i]); } ta.init(a+,n); for(int i=;i<=m;i++) { int ope,a,b; scanf("%d%d%d",&ope,&a,&b); if(ope==) { ta.add(a,b); } else { cout<<ta.query(b)-ta.query(a-)<<endl; } } return ; }樹狀數組2
洛谷-【模闆】樹狀數組 2題目描述
如題，已知一個數列，你需要進行下面兩種操作：
1.将某區間每一個數數加上x
2.求出某一個數的和
輸入輸出格式
輸入格式：
第一行包含兩個整數N、M，分别表示該數列數字的個數和操作的總個數。
第二行包含N個用空格分隔的整數，其中第i個數字表示數列第i項的初始值。
接下來M行每行包含2或4個整數，表示一個操作，具體如下：
操作1： 格式：1 x y k 含義：将區間[x,y]内每個數加上k
操作2： 格式：2 x 含義：輸出第x個數的值
輸出格式：
輸出包含若幹行整數，即為所有操作2的結果。标程
這個題不僅是樹狀數組，當然還使用了線段樹的思想。
修改的時候，隻需要将組成這個區間的幾個節點加這個數（類似于線段樹中的懶操作）。
查詢的時候，依層找自己的上級，然後加上自己上級的值就行了。因為在這裡，上級的值就相當于懶操作的值。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define MAXN 500005 int lb(int k) { return k&(-k); }//lowbit int e[MAXN]; int a[MAXN],n,m; void addto(int x,int v) { while(x>) { e[x]+=v; x-=lb(x); } }//實作1-x區間加v int query(int x) { int ans=a[x]; while(x<=n) { ans+=e[x]; x+=lb(x); } return ans; } int main() { scanf("%d%d",&n,&m); for(int i=;i<=n;i++) scanf("%d",&a[i]); for(int i=;i<=m;i++) { int operate; scanf("%d",&operate); if(operate==) { int a,b,v; scanf("%d%d%d",&a,&b,&v); addto(b,v); addto(a-,-v); } else { int x; scanf("%d",&x); cout<<query(x)<<endl; } } return ; }