TOJ有道題，大意是有N個位置，每個位置有若干瓶子，Mike很淘氣，他每次會增加或減少位置i的瓶子數，然后有M次詢問，求位置A到B的瓶子數的和。最開始，我一直用最直觀的做法，但是由于是O(n)的復雜度，所以一直超時。今天看了BIT的相關東西，才發現那個題其實是典型的BIT題目，而且是最基礎的，但是就和RMQ問題一樣，高效的算法背后深刻的數學理論還是不能很透徹的理解，這個只有靠以后熟練的慢慢來了：D
先來看一下樹狀數組的概念：樹狀數組是一種靜態樹狀數據結構，它的首要作用是維護前綴和，即改變數組中某一元素a[i]的值，若要詢問前N項的和，樹狀數組便可完美解決。時間復雜度O(logn)。
先來直觀看一下樹狀數組的結構（圖片來自http://fqq11679.blog.hexun.com/21722866_d.html#）
在上圖中，紅色的數組c[]便是樹狀數組。改變數組a的某一個元素i，則需要相應的改變數組c，若要詢問前N項和，只需累加相應的c，而這當中一個核心的問題便是相應的數組c的下標問題。可以用位操作lowbit解決。c[i]=a[i-2^k+1]到a[i]的和，k是指i用二進制表示時末位0的個數，即將i表示成冪方和后最小的指數。利用位運算，我們可以得知2^k=i&(i^(i-1));
相應的代碼為：
1 int lowbit(int n)
2 {
3 return n&(n^(n-1));
4 }
這樣，當a[i]改變時，我們只需從c[i]開始一直向上回溯，改變路上相應的數組c的值，若要求前N項和，只需求N以前所有最大子樹c[]的和。然后我們來看相應下標的操作：
修改a[i],則修改一路的父節點c[p], p=i-bit(i);
若要前i項求和，只需一路找子節點c[p], p=i-lowbit(i);
求前N項和：
1 int sum(int n)
2 {
3 int total=0;
4 while(n>0){
5 total+=c[n];
6 n-=lowbit(n);
7 }
8 return total;
9 }
TOJ 3505 Naughty mike
Code：
1 /*TOJ 3505 Naughty mike*/
2 #include<stdio.h> //注意在使用樹狀數組時下標一定不能從0開始
3 #include<string.h>
4 #define M 100002
5 int a[M],n;
6 int c[M];
7 int lowbit(int t) //關鍵的位操作確定數組下標
8 {
9 return t&(t^(t-1));
10 }
11 int sum(int end) //求前end項和的函數，通過不斷累加最大子樹得到
12 {
13 int i;
14 int total=0;
15 while(end>0){
16 total+=c[end];
17 end-=lowbit(end);
18 }
19 return total;
20 }
21 void modify(int t,int key) //對數組某一項進行修改時，只需沿該項一直向上回溯修改相應的數組c
22 {
23 while(t<=n){
24 c[t]+=key;
25 t+=lowbit(t);
26 }
27 }
28 int main()
29 {
30 int i,j,k,m,cas;
31 char e[50];
32 scanf("%d",&cas);
33 while(cas--){
34 scanf("%d",&n);
35 memset(c,0,sizeof(c));
36 for(i=1;i<=n;i++){
37 scanf("%d",&a[i]);
38 modify(i,a[i]);
39 }
40 scanf("%d",&m);
41 while(m--){
42 scanf("%s%d%d",e,&i,&j);
43 if(e[0]=='A'){
44 modify(i,j);
45 a[i]+=j;
46 }
47 else if(e[0]=='D'){
48 if(j>=a[i]) j=(-1)*a[i]; //由于可能刪除的比現有的還多，需要分開考慮
49 else j*=(-1);
50 modify(i,j);
51 a[i]+=j;
52 }
53 else
54 printf("%d\n",sum(j)-sum(i-1)); //區間[i,j]的和
55 }
56 }
57 }
58