created by Dejavu*
[完結(jié)]

• 簡介
  樹狀數(shù)組(Binary Indexed Tree(BIT), Fenwick Tree)是一個查詢和修改復(fù)雜度都為log(n)的數(shù)據(jù)結(jié)構(gòu)。主要用于查詢?nèi)我鈨晌恢g的所有元素之和，但是每次只能修改一個元素的值；經(jīng)過簡單修改可以在log(n)的復(fù)雜度下進行范圍修改，但是這時只能查詢其中一個元素的值。
  　　樹狀數(shù)組十分容易實現(xiàn)，代碼量小，時間復(fù)雜度低，并且經(jīng)過數(shù)學(xué)處理后也可以實現(xiàn)成段更新。線段樹也可以做到和樹狀數(shù)組一樣的效果，但是代碼要復(fù)雜得多。不過要注意，一般情況下樹狀數(shù)組能解決的問題線段樹都能解決，反之有些線段樹能解決的問題樹狀數(shù)組卻不行。
  　　BIT的部分代碼

     int lowbit(int t) {return t&-t;}
     void add(int p,int v) {for(;p<=n;bt[p]+=v,p+=lowbit(p));}
     int sum(int p) {
        int s(0);
        for(;p>0;s+=bt[p],p-=lowbit(p));
        return s;
    }
  

  這里的lowbit作用是取最低位的1，p每次加上lowbit，p都是在加2的整數(shù)倍(除1外)以此來更新與p點數(shù)據(jù)相關(guān)的節(jié)點數(shù)據(jù)，從而快速構(gòu)建起一棵樹，所以n以下最大的lowbit數(shù)將作為頂節(jié)點，而超過最大的lowbit數(shù)時，樹將與最大lowbit數(shù)建立的樹分離，使得計算sum時只能采用分布計算做差來取得結(jié)果

計算區(qū)間[5,9]的和時，sum_out = sum(9)-sum(5-1)

計算過程，例如當(dāng)idx = 13; sum初始 = 0:

• 代碼

  #include <iostream>
  using namespace std;
  #define MAXN 1000
  int n;
  int bt[MAXN] = {0};
  
  int lowbit(int t) {return t&-t;}
  void add(int p,int v) {for(;p<=n;bt[p]+=v,p+=lowbit(p));}
  int sum(int p) {
    int s(0);
    for(;p>0;s+=bt[p],p-=lowbit(p));
    return s;
  }
  
  int main() {
    cin >> n;
    for(int i=1;i<=n;i++) {
        int tmp;cin>>tmp;
        add(i,tmp);
    }
    char cmd;
    int in1,in2;
    while(cin>>cmd,cmd!='E') {
        cin >> in1 >> in2;
        if(cmd == 'Q') cout << sum(in2)-sum(in1-1) <<endl;
        else if(cmd == 'A') add(in1,in2);
    }
  }