樹狀數組簡介（洛谷P3368、P3374）

算法用途

樹狀數組是一個查詢和修改複雜度都為log(n)的資料結構。主要用于查詢任意兩位之間的所有元素之和。

雖然樹狀數組的用途可以完全被線段樹所替代，而且線段樹所能做的比樹狀數組多得多，但是樹狀數組的常數是遠遠小于線段樹的。是以當你寫線段樹被卡常時可以試試使用樹狀數組。

而且樹狀數組的代碼很短哦！

算法思想

開一個數組s，其中s[i]的值存的是a[i-lowbit(i)]~a[i]這段區間的和。然後進行一系列操作。

差不多是這樣一個圖（這裡是c數組）：

像不像一棵樹啊#（滑稽）

關于lowbit

lowbit是什麼啊！看上去好進階的樣子！

low:低，bit:比特（二進位制資訊機關）（其實就是1啦） lowbit就是一個數在二進制中最低的1的位置。

舉個栗子：5在2進制下為101，lowbit(5)=1。8在二進制下為1000，lowbit(8)=4。

那要怎麼算lowbit(x)呢？

給段代碼自己了解下

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

對，你沒看錯，就是這麼簡單！可能會補碼和反碼的同學已經看懂了，這裡給一臉蒙圈的解釋一下。

設x的二進制碼為 1000101011，那麼-x-1的二進制碼就是把x的二進制碼全反過來：0111010100，-x的二進制碼就是：0111010101，x&(-x)=1，就是x的lowbit了。（不信的小夥伴可以自己試試）

單點修改區間求和

單點修改

當a[x]改變時，s[x]會改變，s[x+lowbit(x)]會改變，s[x+lowbit(x)+lowbit(x+lowbit(x))]也會改變······一直到x超過n才停止。

于是我們就可以嘗試寫出代碼：

void nsrt(int x,int w){
    while (x<=n){
        s[x]+=w;
        x+=lowbit(x);
    }
}
           

區間求和

樹狀數組的區間求和運用到了字首和的思想，求l~r的和即求1~r的和減去1~(l-1)的和。

那麼1~x的和怎麼求呢？

前面說過，s[x]存的是a[x-lowbit(x)]~a[x]的和，那麼a[x-lowbit(x)]~a[x]的和我們是已知的，剩下就是求1~(x-lowbit(x))的和，這時s[x-lowbit(x)]又變成了已知，是以和單點修改一樣，區間求和也是一個遞歸的過程，代碼依然很短：

int srch(int x){
    int sum=;
    while(x){
        sum+=s[x];
        x-=lowbit(x);
    }
    return sum;
}
           

模闆

洛谷P3374

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 500000 
using namespace std;
int s[MAXN+];
int next;
int n,m;
int lowbit(int x){
    return x&(-x);
}
void nsrt(int x,int w){
    while (x<=n){
        s[x]+=w;
        x+=lowbit(x);
    }
}
int srch(int x){
    int sum=;
    while(x){
        sum+=s[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=;i<=n;i++){
        int x;
        scanf("%d",&x);
        nsrt(i,x);
    }
    for (int i=;i<=m;i++){
        int flag;
        scanf("%d",&flag);
        if (flag==){
            int x,k;
            scanf("%d%d",&x,&k);
            nsrt(x,k);
        }
        else{
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",srch(y)-srch(x-));            
        }
    }
    return ;
} 
           

區間修改區間求和

百度上說區間修改時隻能求單點值，但是貌似區間也是可以的。。。

因為部落客比較懶中間過程比較煩，這裡部落客就不寫了，

引用一下某大佬的blog

模闆：

洛谷P3368

#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 500000
using namespace std;
int s[MAXN+][];
int n,m;
int lowbit(int x){
    return x&(-x);
}
void nsrt(int l,int r,int w){
    int x;
    r++;
    x=l;
    while (x<=n){
        s[x][]+=w; 
        s[x][]+=w*(l-); 
        x+=lowbit(x);
    }
    x=r;
    while (x<=n){
        s[x][]-=w;
        s[x][]-=w*(r-);
        x+=lowbit(x);
    }
}
int srch(int x){
    int now=x,sum=;
    while (now){
        sum+=x*s[now][]-s[now][];
        now-=lowbit(now);
    }
    return sum;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=;i<=n;i++){
        int x;
        scanf("%d",&x);
        nsrt(i,i,x);
    }
    for (int i=;i<=m;i++){
        int flag;
        scanf("%d",&flag);
        if (flag==){
            int x,y,k;
            scanf("%d%d%d",&x,&y,&k);
            nsrt(x,y,k);
        }
        else{
            int x;
            scanf("%d",&x);
            printf("%d\n",srch(x)-srch(x-));            
        }
    }
    return ;
}
           

如果嫌棄部落客的文章可以看看這位大佬的blog