樹狀數組

作用

樹狀數組可以解決一些區間問題，雖然功能沒有線段樹進階（可以被線段樹完全代替），但是思想簡單，代碼複雜度也很低，常數也很低，低到足以蔑視線段樹。

實作

給出一個長度為n(1<=n<=100000)的序列，提出m(1<=m<=100000)個操作，操作有兩種形式：

Q x y：在x點上加上y(1<=x<=n;-10000<=y<=10000)

C x y：求出序列中x到y(包括x和y)的和(1<=x<=y<=n)

暴力很好想，每次Q操作的時候重新構造字首和，但是效率很低。這時候樹狀數組就派上用場了。

我們建立一個c數組，表示a[i-lowbit(i)]~a[i]這一段的累加和，其中lowbit(i)為i&(-i)，效果是得到2^k，k是i二進制下末尾的0的個數（根據反碼和補碼，-i是i按位取反之後加上1，是以i&(-i)就會得到2^k）那麼：

c[1]=a[1]

c[2]=a[1]+a[2]=c[1]+a[2]

c[3]=a[3]

c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]

c[5]=a[5]

c[6]=a[5]+a[6]=c[5]+a[6]

c[7]=a[7]

c[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]=c[4]+c[6]+c[7]+a[8]

……

這個就是所謂的樹狀數組（發明者是Fenwick，是以也叫Fenwick_Tree），觀察圖就會發現像樹一樣。那麼怎麼使用呢？

單點修改區間求和

1.單點修改

當a[i]改變時，哪些c會改變呢？觀察上面的圖，會發現：c[i]改變,c[i+lowbit(i)]會改變，c[i+lowbit(i)+lowbit(i+lowbit(i))]也會改變……那麼就很容易寫出一個Insert過程：

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

2.區間求和

字首和利用了容斥原理，而樹狀數組區間查詢的目标就是求字首和，再次觀察圖，會發現1~x的字首和就是： c[x]+c[x-lowbit(x)]+c[x-lowbit(x)-lowbit(x-lowbit(x))]+……

（取了c[x]之後，x-lowbit(x)+1~x這一段就都取了，減去lowbit(x)，繼續求1~x-lowbit(x)）

Ask過程也很容易寫出：

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

那麼x~y的區間總和就是Ask(y)-Ask(x-1)。

3.模闆

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=;

int n,te;
struct FenwickTree
{
    int s[maxn+];
    void clear() {memset(s,,sizeof(s));}
    int lowbit(int x) {return x&(-x);}
    void Insert(int x,int tem) {while (x<=n) s[x]+=tem,x+=lowbit(x);}
    int Ask(int x) {int sum=;while (x) sum+=s[x],x-=lowbit(x);return sum;}
};
FenwickTree tr;

char getrch() {char ch=getchar();while (ch!='x'&&ch!='y') ch=getchar();return ch;}
int main()
{
    freopen("FenwickTree.in","r",stdin);
    freopen("FenwickTree.out","w",stdout);
    scanf("%d%d",&n,&te);tr.clear();
    while (te--)
    {
        char td=getrch();int x,y;scanf("%d%d",&x,&y);
        if (td=='x') tr.Insert(x,y); else printf("%d\n",tr.Ask(y)-tr.Ask(x-));
    }
    return ;
}
           

區間增減區間求和

ps：之前根本不知道有這種東西QAQ，見到Lynstery大神寫之後自歎不如啊。

1.區間增減

令c1[i]=a[i]-a[i-1]（好像叫做差分），則增減a[i~j]的時候會發現隻有c1[i]和c1[j+1]改變了，其他都沒變。

然後用c1表示a[i]就是Σc1[1~i]，求a[1~x]就是Σc1[1]+Σc1[1~2]+……Σc1[1~x]。這有何用？繼續看：

Σc1[1]+Σc1[1~2]+……Σc1[1~x]

=(c1[1])+(c1[1]+c1[2])+……+(c1[1]+c1[2]+……+c1[x])

=x*c1[1]+(x-1)*c1[2]+……+c1[x]

=x*(c1[1]+c1[2]+……+c1[x])-(0*c1[1]+1*c1[2]+……+(x-1)*c1[x])

令c2[i]=(i-1)*c1[i]

=x*Σc1[1~x]-Σc2[1~x]

看最後一個式子，又變成字首和了，又因為差分過後隻需要修改c1的兩個節點和c2的兩個節點，是以問題回歸到樹狀數組單點修改！

2.區間求和

和上面的區間求和一樣，隻不過要計算如下式子：

y*Σc1[1~y]-Σc2[1~y]-((x-1)*Σc1[1~x-1]-Σc2[1~x-1])。

3.模闆

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=;

int n,te;
struct FenwickTree
{
    LL s[][maxn+];
    void clear() {memset(s,,sizeof(s));}
    int lowbit(int x) {return x&(-x);}
    void Insert(int L,int R,LL tem)
    {
        int x;R++;
        x=L;while (x<=n) s[][x]+=tem,s[][x]+=tem*(L-),x+=lowbit(x);
        x=R;while (x<=n) s[][x]-=tem,s[][x]-=tem*(R-),x+=lowbit(x);
    }
    LL Ask(int R)
    {
        int x=R;LL sum=;
        while (x) sum+=R*s[][x]-s[][x],x-=lowbit(x);
        return sum;
    }
};
FenwickTree tr;

bool Eoln(char ch) {return ch==||ch==||ch==EOF;}
int readi(int &x)
{
    int tot=,f=;char ch=getchar(),lst='+';
    while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
int readl(LL &x)
{
    LL tot=,f=;char ch=getchar(),lst='+';
    while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
int main()
{
    freopen("FenwickTree.in","r",stdin);
    freopen("FenwickTree.out","w",stdout);
    readi(n);readi(te);
    for (int i=;i<=n;i++)
    {
        LL x;readl(x);
        tr.Insert(i,i,x);
    }
    while (te--)
    {
        int td,x,y;LL z;readi(td);readi(x);readi(y);
        if (td==) readl(z),tr.Insert(x,y,z); else
        printf("%lld\n",tr.Ask(y)-tr.Ask(x-));
    }
    return ;
}
           

效率

好像效率不容易計算，其實我們隻需要從lowbit的角度來看就行了。

對于單點修改，我們需要修改至多 log2(n) 次，為什麼呢？因為第一次取lowbit最小是1，加上1之後，最後一位肯定不是1，然後下一次取lowbit最小是2，加上2之後，最後兩位肯定不是1。以此類推，極端情況下每次lowbit的值會是這樣的：1,2,4,8,……,2^k。是以至多加 log2(n) 次。

對于區間求和，效率也是 log2(n) ，這個很容易分析，因為每次lowbit取到的是2^k（k是二進制下末尾的0的個數），一旦減去2^k，末尾就肯定少掉一個1（二進制），不停少掉1直到變成0為止。而n的二進制最多有 log2(n) 個1，是以至多減 log2(n) 次。

簡單轉化

給出一棵根固定且節點有權值的樹，再給出若幹個操作，有兩種：1.将一個節點的權值改變。2.詢問以一節點為根的子樹權值總和。

遇到這種題目，我們肯定會想到字首和（因為一個節點子樹的權值總和是他所有兒子子樹權值總和加上他自己的權值，類似字首和），但是不知道如何實作，其實仔細想想就發現果斷應該把樹按照Dfs序變成鍊，這樣才可能用字首和。

先Dfs，然後對于i點，記錄int[i]和outt[i]，表示進棧順序和出棧順序，那麼很明顯以i為根的子樹權值總和就是int[i]~outt[i]的區間加和。這樣處理完成之後，就可以用樹狀數組進行優化了。

缺陷

顯然樹狀數組是利用容斥原理的，不能用來處理區間極值（區間極值不滿足容斥原理）等一系列問題。而且區間操作隻能增減，不能乘除或者修改。是以遇到這些問題還是乖乖打線段樹吧。