91人人狠狠,国产探花三级在线观看,2012 91人人

樹狀數(shù)組（Binary Index Tree, BIT）也是很多OIer心中最簡潔優(yōu)美的數(shù)據(jù)結(jié)構(gòu)之一。最簡單的樹狀數(shù)組支持兩種操作，時間復雜度均為 $O(\log+n)$ ：

單點修改：更改數(shù)組中一個元素的值
區(qū)間查詢：查詢一個區(qū)間內(nèi)所有元素的和

當然，樹狀數(shù)組能維護的不局限于加法，支持的操作也不止這兩種，甚至有大佬能用樹狀數(shù)組實現(xiàn)平衡樹，但這篇筆記不會深入討論（因為我也還不是很懂hh）。

我們還是先來看一道模板題，來看看樹狀數(shù)組最基本的應用場景：

（HDU P1166）敵兵布陣

Problem Description
C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報局要研究敵人究竟演習什么戰(zhàn)術(shù),所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總?cè)藬?shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數(shù)，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這么慢，我炒你魷魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我魷魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現(xiàn)在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經(jīng)掛掉電話了。Tidy很苦惱，這么算他真的會崩潰的，聰明的讀者，你能寫個程序幫他完成這項工作嗎？不過如果你的程序效率不夠高的話，Tidy還是會受到Derek的責罵的.
Input
第一行一個整數(shù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)第一行一個正整數(shù)N（N<=50000）,表示敵人有N個工兵營地，接下來有N個正整數(shù),第i個正整數(shù)ai代表第i個工兵營地里開始時有ai個人（1<=ai<=50）。
接下來每行有一條命令，命令有4種形式：
(1) Add i j,i和j為正整數(shù),表示第i個營地增加j個人（j不超過30）
(2)Sub i j ,i和j為正整數(shù),表示第i個營地減少j個人（j不超過30）;
(3)Query i j ,i和j為正整數(shù),i<=j，表示詢問第i到第j個營地的總?cè)藬?shù);
(4)End 表示結(jié)束，這條命令在每組數(shù)據(jù)最后出現(xiàn);
每組數(shù)據(jù)最多有40000條命令
Output
對第i組數(shù)據(jù),首先輸出“Case i:”和回車,
對于每個Query詢問，輸出一個整數(shù)并回車,表示詢問的段中的總?cè)藬?shù),這個數(shù)保持在int以內(nèi)。

這個數(shù)據(jù)范圍，直接模擬肯定會T，所以我們要使用數(shù)據(jù)結(jié)構(gòu)來維護數(shù)組，樹狀數(shù)組可以說是其中最簡潔的一種。我們來看看樹狀數(shù)組是怎么實現(xiàn)的。

樹狀數(shù)組的引入

回顧一下，我們說，我們要實現(xiàn)兩種操作：單點修改和區(qū)間求和。對于普通數(shù)組而言，單點修改的時間復雜度是 $O(1)$ ，但區(qū)間求和的時間復雜度是 $O(n)$ 。

img

普通數(shù)組

當然，我們也可以用前綴和的方法維護這個數(shù)組，這樣的話區(qū)間求和的時間復雜度就降到了 $O(1)$ ，但是單點修改會影響后面所有的元素，時間復雜度是 $O(n)$ 。

img

程序最后跑多長時間，是由最慢的一環(huán)決定的，因此現(xiàn)在我們希望找到這樣一種折中的方法：無論單點修改還是區(qū)間查詢，它都能不那么慢地完成。

注意到對 $[a,b]$ 進行區(qū)間查詢只需查詢 $[1,b]$ 和 $[1,a)$ 然后相減即可（前綴和就是這樣進行區(qū)間查詢的），所以我們可以把區(qū)間查詢問題轉(zhuǎn)化為求前n項和的問題。

關于數(shù)組的維護，有個很自然的想法：可以用一個數(shù)組 $C$ 維護若干個小區(qū)間，單點修改時，只更新包含這一元素的區(qū)間；求前n項和時，通過將區(qū)間進行組合，得到從1到n的區(qū)間，然后對所有用到的區(qū)間求和。實際上，設原數(shù)組是 $A$ ，如果 $C_i$ 維護的區(qū)間是 $[A_i,+A_i]$ ，此結(jié)構(gòu)就相當于普通數(shù)組（還浪費了一倍內(nèi)存）；如果 $C_i$ 維護的區(qū)間就是 $[1,A_i]$ ，此結(jié)構(gòu)就相當于前綴和。

現(xiàn)在我們試圖尋找一種結(jié)構(gòu)，一方面，單點修改時需要更新的區(qū)間不會太多；另一方面，區(qū)間查詢時需要用來組合的區(qū)間也不會太多。

樹狀數(shù)組就是這樣一種結(jié)構(gòu)，它巧妙地利用了二進制（實際上，樹狀數(shù)組的英文名BIT，直譯過來就是二進制下標樹）。例如11，轉(zhuǎn)化為二進制數(shù)就是 $(1011)_2$ ，如果我們要求前11項和，可以分別查詢 $\big(+\left(0000\right)_2+,+\left(1000\right)_2+\big]$ 、 $\big(+\left(1000\right)_2+,+\left(1010\right)_2+\big]$ 以及 $\big(+\left(1010\right)_2+,+\left(1011\right)_2+\big]$ 的和再相加。這三個區(qū)間怎么來的呢？其實就是不斷地去掉二進制數(shù)最右邊的一個1的過程（如下圖）。

img

我們定義，二進制數(shù)最右邊的一個1，連帶著它之后的0為 $\text{lowbit}(x)$ （稍后再來看如何實現(xiàn)）。那么我們用 $C_i$ 維護區(qū)間 $(A_i-\text{lowbit}(A_i),A_i]$ ，這樣顯然查詢前n項和時需要合并的區(qū)間數(shù)是少于 $\log_2{n}$ 的。樹狀數(shù)組的結(jié)構(gòu)大概像下面這樣：

img

那么如何更新呢，大家會發(fā)現(xiàn)更新就是一個“爬樹”的過程。一路往上更新，直到MAXN（樹狀數(shù)組的容量）。

img

我們舉個例子來看看這樹是怎么爬的。現(xiàn)有二進制數(shù) $(100110)_2$ ，包含它的最小區(qū)間當然是 $\big(+\left(100100\right)_2+,+\left(100110\right)_2+\big]$ 。然后，它也肯定位于區(qū)間 $\big(+\left(100000\right)_2+,+\left(101000\right)_2+\big]$ 內(nèi)。然后是 $\big(+\left(100000\right)_2,+\left(110000\right)_2+\big]$ ，再然后是 $\big(+0+,+\left(1000000\right)_2+\big]$ ……

img

如上圖，每一步都把從右邊起一系列連續(xù)的1變?yōu)?，再把這一系列1的前一位0變?yōu)?。這看起來像是一個進位的過程對吧？實際上，每一次加的正是 $\text{lowbit}(x)$ 。（神奇吧？）這樣，我們更新的區(qū)間數(shù)不會超過 $\log_2{\small+\text{MAXN}}$ 。一個能以 $O(\log{n})$ 時間復雜度進行單點修改和區(qū)間查詢的數(shù)據(jù)結(jié)構(gòu)就誕生了。

樹狀數(shù)組的實現(xiàn)

前面已經(jīng)講得很詳細了，代碼實現(xiàn)倒是一件簡單的事了。不過我們需要先解決一個問題：lowbit怎么算？如果一位一位驗證的話，會形成額外的時間開銷。然而，我們有這樣神奇的一個公式：

$\text{lowbit}(x)=(x)\&(-x)$

為什么可以這樣？我們需要知道，計算機里有符號數(shù)一般是以補碼的形式存儲的。-x相當于x按位取反再加1，會把結(jié)尾處原來1000...的形式，變成0111...，再變成1000...；而前面每一位都與原來相反。這時我們再把它和x按位與，得到的結(jié)果便是lowbit(x)。下面的圖中舉了兩個例子：

img

現(xiàn)在我們可以愉快地實現(xiàn)樹狀數(shù)組了：

單點修改

int tree[MAXN];
inline void update(int i, int x)
{
    for (int pos = i; pos < MAXN; pos += lowbit(pos))
        tree[pos] += x;
}

求前n項和

inline int query(int n)
{
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos))
        ans += tree[pos];
    return ans;
}

區(qū)間查詢

inline int query(int a, int b)
{
    return query(b) - query(a - 1);
}

初始化的時候，我們只需要update每個點的初始值即可。

樹狀數(shù)組的應用

還是先來看文章一開始那道題目的AC代碼：

#include <cstdio>
#include <cstring>
#define MAXN 50005
#define lowbit(x) ((x) & (-x))
int tree[MAXN];
inline void update(int i, int x)
{
    for (int pos = i; pos < MAXN; pos += lowbit(pos))
        tree[pos] += x;
}
inline int query(int n)
{
    int ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos))
        ans += tree[pos];
    return ans;
}
inline int query(int a, int b)
{
    return query(b) - query(a - 1);
}
int main()
{
    int cases;
    scanf("%d", &cases);
    for (int I = 1; I <= cases; ++I)
    {
        memset(tree, 0, sizeof(tree));
        int n, x, a, b;
        char opr[10];
        printf("Case %d:\n", I);
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &x);
            update(i, x);
        }
        while (scanf("%s", opr), opr[0] != 'E')
        {
            switch (opr[0])
            {
            case 'A':
                scanf("%d%d", &a, &b);
                update(a, b);
                break;
            case 'S':
                scanf("%d%d", &a, &b);
                update(a, -b);
                break;
            case 'Q':
                scanf("%d%d", &a, &b);
                printf("%d\n", query(a, b));
            }
        }
    }
    return 0;
}

然而，這只是樹狀數(shù)組最基本的應用。樹狀數(shù)組的應用是非常廣泛的，例如，非常常見的一個應用是求逆序?qū)?/strong>：

（洛谷P1908）逆序?qū)?/strong>

題目描述
貓貓TOM和小老鼠JERRY最近又較量上了，但是畢竟都是成年人，他們已經(jīng)不喜歡再玩那種你追我趕的游戲，現(xiàn)在他們喜歡玩統(tǒng)計。最近，TOM老貓查閱到一個人類稱之為“逆序?qū)Α钡臇|西，這東西是這樣定義的：對于給定的一段正整數(shù)序列，逆序?qū)褪切蛄兄衋i>aj且i<j的有序?qū)?。知道這概念后，他們就比賽誰先算出給定的一段正整數(shù)序列中逆序?qū)Φ臄?shù)目。
輸入格式
第一行，一個數(shù)n，表示序列中有n個數(shù)。
第二行n個數(shù)，表示給定的序列。序列中每個數(shù)字不超過10^9
輸出格式
給定序列中逆序?qū)Φ臄?shù)目。

當然逆序?qū)σ部梢杂脷w并排序的方法求，但樹狀數(shù)組的空間復雜度更低。其實我們與其說在用樹狀數(shù)組求逆序?qū)?，不如說是在求非嚴格順序?qū)?/strong>（順序?qū)拖嗟葘Γ?，然后間接算出逆序?qū)Φ臄?shù)量。我們是怎么算出非嚴格順序?qū)Φ膫€數(shù)的呢？

例如，我們要求5 4 1 3 2的逆序?qū)ΑＳ胊ns記錄非嚴格順序?qū)Φ臄?shù)量。

img

我們按順序去填充樹狀數(shù)組，第一個數(shù)字是5，這時沒有數(shù)比5小，所以ans保持為0。我們把tree[5]填為1。

img

下一個數(shù)字是1，這時也沒有數(shù)比1小，ans仍為0。我們把tree[1]填為1。

img

下一個數(shù)字是3，這時query(3)為1，有一個數(shù)比3小了，ans變?yōu)?。然后再填tree[3]。

img

下一個數(shù)字是2，這時query(2)為1，說明前面有一個數(shù)比2小，ans再加1變?yōu)?。然后填tree[2]。

img

最后一個數(shù)字是4，query(4)為3，說明前面有3個數(shù)比4小，ans加3變?yōu)?。所以非嚴格順序?qū)Φ目倲?shù)就是5。那么逆序?qū)灿? $C_5^2-5=5$ 個。

img

當然，這道逆序?qū)Φ念}還涉及到離散化等問題，這個以后可能我也會寫相關筆記。完整代碼如下：

#include <cstdio> #include <cctype> #include <algorithm> #define lowbit(x) ((x) & (-x)) #define MAXN 500010 using namespace std; typedef long long ll; ll read() //快速讀入，不是這篇文章的重點 { ll ans = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { ans = ans * 10 + c - '0'; c = getchar(); } return ans; } ll tree[MAXN]; inline void update(ll i, ll x) { for (ll pos = i; pos < MAXN; pos += lowbit(pos)) tree[pos] += x; } inline ll query(int n) { ll ans = 0; for (ll pos = n; pos; pos -= lowbit(pos)) ans += tree[pos]; return ans; } inline ll query(ll x, ll y) { return query(y) - query(x - 1); } int A[MAXN]; //離散化后的數(shù)組 typedef struct { ll value, id; } mypair; mypair B[MAXN]; //原始數(shù)組（同時存儲id） bool cmp(mypair x, mypair y) { if (x.value < y.value) return true; else if (x.value == y.value && x.id < y.id) return true; return false; } int main() { ll n = read(), sum = 0; for (int i = 1; i <= n; i++) { B[i].value = read(); B[i].id = i; } sort(B + 1, B + n + 1, cmp); for (int i = 1; i <= n; i++) A[B[i].id] = i; for (int i = 1; i <= n; i++) { update(A[i], 1); sum += query(A[i]); } sum = n / 2 * (n + 1) - sum; printf("%lld\n", sum); return 0; }

這里面還寫了一個快速讀入，可以不必太在意，重點還是在于這段代碼：

for (int i = 1; i <= n; i++) { update(A[i], 1); sum += query(A[i]); }

其實單單是對這個求逆序?qū)Φ耐卣箲茫陀胁簧兕}目了，可見這個樹狀數(shù)組的應用面是多么廣泛。但這篇文章已經(jīng)很長了（我水平也有限），就先寫到這兒吧。