天天看點
傳回

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

資料結構_樹狀數組 詳解

😀 Powerd By HeartFireY | -Binary Indexed Tree- |

文章目錄

  • 資料結構_樹狀數組 詳解
    • 一、簡介/前導
      • 1.前導
      • 2.簡介
    • 二、樹狀數組 詳解
      • 1.區間查詢 詳解
      • 2.單點修改 詳解
      • 3.兩種操作的具體實作
    • 三、樹狀數組 總結
      • 1.樹狀數組 - 區間加 區間求和
      • 2.樹狀數組 - O ( log ⁡ n ) O(\log n) O(logn)查詢第 k k k小/大元素
      • 3.時間戳優化

一、簡介/前導

1.前導

我們來關注這樣一個問題：要求對一個數組實作單點修改、區間求和。

我們不難得知：在樸素算法下，單點修改的時間複雜度 O ( 1 ) O(1) O(1)，區間求和的時間複雜度 O ( n ) O(n) O(n)。

如果使用字首和進行優化，區間求和的時間複雜度降為 O ( 1 ) O(1) O(1)，而單點修改的時間複雜度卻變為 O ( n ) O(n) O(n)。

顯然，在強資料下，這兩種算法是容易超出所給時間範圍的。

如果我們使用一個數組來維護每一段區間的和，對所有需要用到的區間進行求和，但如果要查詢或修改的區間跨度大，則會引起大量的區間更新、合并操作。顯然這也是不明智的選擇。

是以，我們想要尋找一種折中的方案，使得區間求和和單點修改的時間複雜度都不會太大。那麼我們需要考慮引起時間開銷的原因：

對于單點修改，在字首和下需要對區間進行更新操作；對于區間求和，在樸素算法下需要對區間内的子區間進行合并操作。

那麼我們能否找到這樣一種結構：單點修改時引發的區間更新數量不會太多、區間查詢時需要進行合并的對象不會太多，那麼這就需要引出我們本篇文章的主要對象：樹狀數組(BIT)。

2.簡介

樹狀數組(Binary Indexed Tree)又稱二叉搜尋樹，簡稱BIT。

樹狀數組是這樣一種資料結構：在 O ( log ⁡ n ) O(\log n) O(logn)時間複雜度下，支援單點修改、區間查詢的一種儲存結構。

對于樹狀數組，我們很容易聯系到線段樹：線段樹支援單點修改、區間修改、區間查詢。同時在 L a z y Lazy Lazy标記的輔助下，能夠實作很優秀的區間修改算法。如下是一棵線段樹的結構：

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

但是在許多場景下，我們并不要進行區間修改，僅僅是進行簡單的單點修改和區間查詢，是以我們可以引入樹狀數組。與線段樹相比，樹狀數組的代碼更為簡潔，在解決一類問題(單點修改)時具有突出的優勢。如下是一個樹狀數組的結構示意圖：

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

我們通過這張圖對樹狀數組的結構進行分析，并介紹具體的原理。

這裡可能會引發一個疑問：上圖實際上并不是一棵二叉樹？

我們通過一個動畫來解釋這個問題：

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

二、樹狀數組 詳解

1.區間查詢 詳解

首先，我們給出一個長度為 8 8 8的數組(為了計算友善，我們約定下标從 1 1 1開始)。其樹狀數組結構如下圖所示：

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

現在我們複現一下一開始提出的問題，單點修改，區間求和。

如果我們要求前 8 8 8項的和，那麼我們需要查詢的區間是 ( ( 0000 ) 2 , ( 1000 ) 2 ] ((0000)_2,(1000)_2] ((0000)2​,(1000)2​]；

如果我們要求前7項的和，那麼我們需要查詢的區間是 ( ( 0000 ) 2 , ( 0100 ) 2 ] , ( ( 0100 ) 2 , ( 0110 ) 2 ] , ( ( 0110 ) 2 , ( 0111 ) 2 ] ((0000)_2,(0100)_2],((0100)_2, (0110)_2],((0110)_2, (0111)_2] ((0000)2​,(0100)2​],((0100)2​,(0110)2​],((0110)2​,(0111)2​];

. . . ... ...

查詢的區間是如何得到的？區間右端點不斷地取最低為 1 1 1的位并改為 0 0 0，作為左端點，直到沒有 1 1 1(即為 0 0 0)時結束。

我們再學習狀态壓縮的時候曾經使用過這樣一個函數 l o w b i t ( x ) lowbit(x) lowbit(x)，它的作用是傳回 x x x二進制表示中最低位為 0 0 0的數。

這麼做的依據是什麼？我們回到結構圖中，很顯然可以看出：

c 2 c_2 c2​ 管理的對象是 a 1 a_1 a1​& a 2 a_2 a2​；

c 4 c_4 c4​ 管理的對象是 a 1 a_1 a1​& a 2 a_2 a2​& a 3 a_3 a3​& a 4 a_4 a4​；

c 6 c_6 c6​ 管理的對象是 a 5 a_5 a5​& a 6 a_6 a6​；

c 8 c_8 c8​ 則管理全部 8 8 8 個數。

如果我們要求前 7 7 7項的和，我們從 c 7 c_7 c7​開始， c 7 c_7 c7​隻管理一個點 a 7 a_7 a7​；繼續向前找會找到 c 6 c_6 c6​，而 c 6 c_6 c6​管理 a 5 a_5 a5​& a 6 a_6 a6​；那麼我們跳過被管理的元素繼續向前找會找到 c 4 c_4 c4​，管理的是 a 1 a_1 a1​& a 2 a_2 a2​& a 3 a_3 a3​& a 4 a_4 a4​。那麼顯然，查詢操作結束。不難發現：查詢的過程被不停的壓縮優化。

那麼我們隻需要通過 c i c_i ci​維護區間 ( a i − l o w b i t ( a i ) , a i ] (a_i - lowbit(a_i), a_i] (ai​−lowbit(ai​),ai​]，這樣在查詢前合并的區間數是小于 log ⁡ 2 n \log_2 n log2​n的。我們将 a a a數組和 c c c數組的對應關系用結構圖進行說明：

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

2.單點修改 詳解

解決了區間查詢的問題，我們來解決單點修改的問題。如何維護樹狀數組 c c c呢？

假如我們要對 A [ 5 ] A[5] A[5]進行修改，那麼我們從 c 5 c_5 c5​出發，沿着 c 5 → c 6 → c 8 c_5 \rightarrow c_6 \rightarrow c_8 c5​→c6​→c8​的路徑進行修改。這條路徑是怎樣得到的？

資料結構_樹狀數組 詳解資料結構_樹狀數組 詳解

我們将下标二進制化，再來觀察路徑： c [ 0101 ] → c [ 0110 ] → c [ 1000 ] c[0101] \rightarrow c[0110] \rightarrow c[1000] c[0101]→c[0110]→c[1000]，不難發現：更新路徑上相鄰結點 c i c_i ci​ 和 c i + 1 c_{i + 1} ci+1​ 剛好相差一個 l o w b i t ( i ) lowbit(i) lowbit(i)，那麼更新的過程就很簡單了，循環取 l o w b i t ( i ) lowbit(i) lowbit(i)更新 c i 、 c i + l o w b i t ( i ) . . . c_i、c_{i + lowbit(i)}... ci​、ci+lowbit(i)​...直到 i = M A X N i = MAXN i=MAXN ( M A X N MAXN MAXN為數組長度)。

這樣，我們就得到了一種可以在 O ( log ⁡ n ) O(\log n) O(logn)時間下支援單點修改和區間查詢的資料結構。

3.兩種操作的具體實作

經過上述分析，我們可以對兩種操作進行實作：

#define lobit(x) ((x) & (-x))
#define MAXN $Array_Max_Sizes$
int a[MAXN], len;
int tree[MAXN];
//樹狀數組初始化(O(n)建樹)
inline void init(){
    memset(tree, 0, sizeof(tree));
    for(int i = 1, tmp = 0; i <= len; i++){
        tree[i] = a[i];
        tmp = i + lowbit(i);
        if(tmp <= n) tree[tmp] += tree[i];
    }
}
//單點修改-更新路徑
inline void update(int i, int x){
    for(int pos = i; pos <= len; pos += lowbit(pos)) tree[pos] += x;
}
//求前n項和
inline int getsum(int i){
    int ans = 0;
    for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}
//區間查詢
inline int query(int l ,int r){
    return getsum(b) - getsum(a - 1);
}

不難發現，幾種操作都十分簡單(相比于線段樹)，是以樹狀數組在解決單純的“單點修改+區間查詢”問題時是非常優秀的資料結構。

三、樹狀數組 總結

1.樹狀數組 - 區間加 區間求和

在上述的操作中，我們對于區間求和的過程是基于樸素求和得到的，如果僅僅針對區間加和區間求和這一種應用方式，我們可以通過字首和與差分對這一過程繼續進行優化：

若維護序列 a a a 的差分數組 b b b，此時我們對 a a a 的一個字首 r r r 求和，即 ∑ i = 1 r a i \sum_{i=1}^{r} a_i ∑i=1r​ai​，由差分數組定義得 a i = ∑ j = 1 i b j a_i=\sum_{j=1}^i b_j ai​=∑j=1i​bj​

進行推導

∑ i = 1 r a i = ∑ i = 1 r ∑ j = 1 i b j = ∑ i = 1 r b i × ( r − i + 1 ) = ∑ i = 1 r b i × ( r + 1 ) − ∑ i = 1 r b i × i \begin{aligned} &\sum_{i=1}^{r} a_i\\=&\sum_{i=1}^r\sum_{j=1}^i b_j\\=&\sum_{i=1}^r b_i\times(r-i+1) \\=&\sum_{i=1}^r b_i\times (r+1)-\sum_{i=1}^r b_i\times i \end{aligned} ===​i=1∑r​ai​i=1∑r​j=1∑i​bj​i=1∑r​bi​×(r−i+1)i=1∑r​bi​×(r+1)−i=1∑r​bi​×i​

區間和可以用兩個字首和相減得到，是以隻需要用兩個樹狀數組分别維護 ∑ b i \sum b_i ∑bi​ 和 ∑ i × b i \sum i \times b_i ∑i×bi​，就能實作區間求和。

#define lobit(x) ((x) & (-x))
#define MAXN $Array_Max_Sizes$
int tree1[MAXN], tree2[MAXN], a[MAXN], len;
//建樹，這裡不用0(n)建樹
inline void init(){
    for(int i = 1; i <= len; i++) update(i, a[i]), update(i + 1， -x);
}
//對兩個樹狀數組進行更新
inline void add(int i, int x){
    int x1 = i * x;
    for(int pos = i; pos <= len; pos += lowbit(pos)) tree1[pos] += x, tree2[pos] += x1;
}
//将區間加差分為兩個字首和
inline void update(int l, int r, int x){
    add(l, x), add(r + 1, -x);
}
//對指定的樹狀數組求前n項和
inline int getsum(int *tree, int i){
    int sum = 0;
    for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[i];
    return sum;
}
//區間和查詢
inline int query(int l, int r){
    return (r + 1) * getsum(t1, r) - l * getsum(t1, l - 1) - (getsum(t2, r) - getsum(t2, l - 1));
}

2.樹狀數組 - O ( log ⁡ n ) O(\log n) O(logn)查詢第 k k k小/大元素

在此以第 k k k小的元素為例。若求第 k k k大則可以通過簡單計算進行轉化。

我們需要再次借用線段樹中的思想。我們在可持久化線段樹中，在求區間第 k k k小時，将所有數字看成一個可重集合，即定義數組 a a a 表示值為 i i i 的元素在整個序列重出現了 a i a_i ai​ 次。找第 k k k 大就是找到最小的 x x x 恰好滿足 ∑ i = 1 x a i ≥ k \sum_{i=1}^{x}a_i \geq k ∑i=1x​ai​≥k

是以可以想到算法：如果已經找到 x x x 滿足 ∑ i = 1 x a i ≤ k \sum_{i=1}^{x}a_i \le k ∑i=1x​ai​≤k，考慮能不能讓 x x x 繼續增加，使其仍然滿足這個條件。找到最大的 x x x 後， x + 1 x+1 x+1 就是所要的值。

在樹狀數組中，節點是根據 2 的幂劃分的，每次可以擴大 2 的幂的長度。令 s u m sum sum 表示目前的 x x x 所代表的字首和，有如下算法找到最大的 x x x：

  1. 求出 d e p t h = ⌊ log ⁡ 2 n ⌋ depth=\left \lfloor \log_2n \right \rfloor depth=⌊log2​n⌋
  2. 計算 t = ∑ i = x + 1 x + 2 d e p t h a i t=\sum_{i=x+1}^{x+2^{depth}}a_i t=∑i=x+1x+2depth​ai​
  3. 如果 s u m + t ≤ k sum+t \le k sum+t≤k，則此時擴充成功，将 2 d e p t h 2^{depth} 2depth 累加到 x x x 上；否則擴充失敗，對 x x x 不進行操作
  4. 将 d e p t h depth depth 減 1，回到步驟 2，直至 d e p t h depth depth 為 0 
int kth(int i){
    int cnt = 0, ret = 0;
    for (int i = log2(len); ~i; --i){                           // i與上文depth含義相同
        ret += 1 << i;                                          // 嘗試擴充
        if (ret >= len || cnt + tree[ret] >= i)  ret -= 1 << i; //擴充失敗
        else cnt += tree[ret]; // 擴充成功後 要更新之前求和的值
    }
    return ret + 1;
}

3.時間戳優化

時間戳優化有什麼用？

我們經常碰到多組輸入的題目，按照一般操作，每次輸入新資料後我們會 m e m s e t memset memset暴力清空數組。但如果每次輸入新資料時，都暴力清空樹狀數組，就可能會造成逾時。

是以使用 t a g tag tag 标記，存儲目前節點上次使用時間（即最近一次是被第幾組資料使用）。每次操作時判斷這個位置 t a g tag tag 中的時間和目前時間是否相同，就可以判斷這個位置應該是 0 還是數組内的值。

#define lowbit(x) ((x) & (-x)
#define MAXN $Array_Max_Size$
int tag[MAXN], t[MAXN], Tag, len;
void reset() { ++Tag; }
void update(int k, int v){
    while (k <= len){
        if (tag[k] != Tag) t[k] = 0;
        t[k] += v, tag[k] = Tag;
        k += lowbit(k);
    }
}
int getsum(int k){
    int ret = 0;
    while (k){
        if (tag[k] == Tag) ret += t[k];
        k -= lowbit(k);
    }
    return ret;
}
t[k] = 0;
        t[k] += v, tag[k] = Tag;
        k += lowbit(k);
    }
}
int getsum(int k){
    int ret = 0;
    while (k){
        if (tag[k] == Tag) ret += t[k];
        k -= lowbit(k);
    }
    return ret;
}
算法學習 資料結構 算法 樹結構
上一篇: 【資料結構】樹狀數組
下一篇: java 16進制字元串轉byte數組_Java轉換byte[]數組、Hex十六進制字元串

繼續閱讀