跳轉到

BIT

前置知識

負號的二進制

每位 01 互換再加 1, 可以轉換正負號，ex. 3 和 -3

Image title

lowbit 介紹

lowbit(x) : 二進制最靠右的 1

例如 6 = 0110，lowbit(6) = 0010

lowbit 運算

lowbit(x) = x & (-x)

Image title

引入

BIT 一定要是 1-base

query

query(x) : 求 a[1, x] 區間的和

code 
1
2
3
4
5
6
7
8
int query(int x) {
    int ret = 0;
    while (x > 0) {
        ret += bit[x];
        x -= lowbit(x);
    }
    return ret;
}

modify

modify(x, d) : a[x] 加上 d

code 
1
2
3
4
5
6
void modify(int x, int d) {
    while (x <= n) {
        bit[x] += d;
        x += lowbit(x);
    }
}

模板

code 
 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
struct BIT {
    #define lowbit(x) (x & (-x))
    int n;
    vector<int> bit;

    void build(int _n) {
        n = _n;
        bit.resize(n + 1);
    }
    int query(int x) {
        int ret = 0;
        while (x > 0) {
            ret += bit[x];
            x -= lowbit(x);
        }

        return ret;
    }
    void add(int x, int d) {
        while (x <= n) {
            bit[x] += d;
            x += lowbit(x);
        }
    }
};

BIT 支援操作

query 的區間只能是前綴, 僅能回答可由前綴組合出來的問題

  1. 區間求和, 單點加值
  2. 單點求和, 區間加值
  3. 區間求和, 區間加值

區間求和, 單點加值

註 : 其實把加值變化一下可以支援單點改值

單點求和, 區間加值

把 bit 的看成是前綴和陣列，區間加值就用差分改兩個點，單點求和時就求 bit[1] + ... + bit[i]