Fenwick Tree

相較於前綴和只能用來查詢區間和
當我們想要修改某項數值時，就需要重新處理一次
前綴和的 O(1) 求區間和，無法滿足大量的修改操作
這時候可以使用 Fenwick Tree 來快速的修改、求總和
Fenwick Tree 可以在 O(n) 的時間初始化，並且在 O(log n) 的時間查詢區間和、修改其中一項元素的值

別名：Binary Indexed Tree、BIT、樹狀數組

要點

功能

  • update：更新某項元素的值
  • query：查詢某範圍的區間和

lowbit

lowbit 是整個資料結構的核心
假如 n = ，那 n 的二進制表示法就是
這時候 n 可以拆分成 + ，則 n 的 lowbit 就是 （取最小的位元）
從二進制上可以直接理解為 10010 的 lowbit 是 10

觀念

我們會需要兩個一維陣列 v 跟 bit
v：原數列
BIT：預處理後的數列

最後可以藉由 bit 陣列求出前綴和並計算該區間和

因為位元計算 lowbit 及前綴求區間和，BIT 陣列也是 1-based

底下是 BIT 的圖解

圖片引用自 這裡

只要將 v 中的所有元素取 index 的二進制中所有為 1 的 bit
當作 BIT 的 index，將其值增加 v 的數值
就可以將 BIT 建表

實作

Fenwick Tree 會用到的變數、陣列
這次範例會開在全域，讓函式可以直接存取

n 為原陣列的長度

1
2
vector<int> v, BIT;
int n;

lowbit

可以對相反數做 & 運算來實作 lowbit
且可以利用 define 來增加程式碼的可讀性

1
#define lowbit(x) ((x)&-(x))

update 函式

原數列 v 的改變要映射到 BIT 數列
其實就是對受影響的區間增加 / 減少 v 的值

1
2
3
void upd(int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) bit[idx] += val;
}

如果想要更改某項 v 數列中的值
則可以刪除原本的值，再增加新的值

1
2
3
upd(a, v[a]);
v[a] = b;
upd(a, b);

建表

而建表其實就是對在 v 中的每項數值
在 BIT 內更新一次

1
2
3
4
5
6
void build() {
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        upd(i, v[i]);
    }
}

查詢

從 BIT 查詢區間和 [a, b]，需要從 BIT 裡面取兩次前綴和
也就是 [1, b] 減去 [1, a-1]

1
2
3
4
5
6
int query(int a, int b) {
    int sa = 0, sb = 0; a--;
    for (; b > 0; b -= lowbit(b)) sb += bit[b];
    for (; a > 0; a -= lowbit(a)) sa += bit[a];
    return sb-sa;
}

範例

題目：HDU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) ((x)&-(x))

vector<int> v, bit;
int n;

void add(int idx, int val) {
    for (; idx <= n; idx += lowbit(idx)) bit[idx] += val;
}

int get(int start, int end) {
    int a = 0, b = 0;
    start--;
    for (; start > 0; start -= lowbit(start)) a += bit[start];
    for (; end > 0; end -= lowbit(end)) b += bit[end];
    return b-a;
}

signed main() { ios::sync_with_stdio(0); cin.tie(0);
    int t, i;
    for (cin >> t, i = 1; i <= t; i++) {
        cout << "Case " << i << ":\n";
        cin >> n;
        v.resize(n);
        for (auto &i : v) cin >> i;
        bit.resize(n+1, 0);
        for (int i = 0; i < n; i++) add(i+1, v[i]);

        string cmd;
        int a, b;
        while (cin >> cmd) {
            if (cmd == "End") break;
            cin >> a >> b;
            if (cmd == "Query") cout << get(a, b) << '\n';
            else if (cmd == "Add") add(a, b);
            else if (cmd == "Sub") add(a, -b);
        }
        v.clear(); bit.clear();
    }
}

用 BIT 求逆序數

逆序數

逆序數是指一個數列中，滿足 i < j 且第 i 個數小於第 j 個數的數對數量
簡單來說就是