【筆記】Binary Indexed Tree 樹狀數組

  • 【用途】計算動態「前綴和」,比線段樹更節省記憶體,也更容易實作。
  • 【概念】給定一個陣列 A[ ] = {A1, A2, A3, A4, A5, A6, A7, A8, A9}
    • 計算區間和 sum({A3, A4, A5, A6}) = sum({ A1, A2, A3, A4, A5, A6}) – sum({A1, A2})
    • 只要對任意的 i,都能算出前綴和 sum({A1, …, Ai}),就可以求得任意區間和。
  • 【複雜度】
    • 時間複雜度:O(log(N))
    • 空間複雜度:O(N)
  • 【實作】update(x, d):更新 BIT 的值 (第 x 項的值加上 d, delta),下圖以A13 + d為例。
    • 關鍵計算:x += x & (-x)
    • BIT數組中的B[13], B[14], B[16] 都包含A13,因此必須一併更新。
void update(int x, int d){
    // update prefix sum in BIT
    while(x <= N){
        b[x] += d;
        x += x & (-x);
    }
}
  • 【實作】query(x):利用BIT 計算前 x 項的和,下圖以 sum({A1, A2, …, A13})為例。
  • 關鍵計算:x -= x & (-x)
  • 答案為BIT數組中的 B[13] + B[12] + B[8]。
int query(int x){
    // 以 BIT 計算和
    int ret = 0;
    while (x){
        ret += b[x];
        x -= x & (-x);
    }
    return ret;
}

【範例】ZeroJudge d794: 世界排名題解
【解題想法】數值離散化 + BIT

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long

int N, M;
int b[100001]; //BIT
vector<ll> v, d;

int getID(ll x){
    //離散化
    return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
}

int query(int x){
    // query prefix sum in BIT
    int ret = 0;
    while (x){
        ret += b[x];
        x -= x & (-x);
    }
    return ret;
}

void update(int x, int d){
    // update prefix sum in BIT
    while(x <= N){
        b[x] += d;
        x += x & (-x);
    }
}

int main(){
    while (cin >> N){
        for (int i=1; i<=N; i++){
            b[i] = 0; //clear BIT
        }

        v.clear();
        for (int i=0; i<N; i++){
            cin >> M;
            v.push_back(M);
        }
        d = v;
        sort(d.begin(), d.end());
        // 去除重複的數字
        // d.erase(unique(d.begin(), d.end()), d.end());
        for (int i=1; i<=N; i++) {
            int idx = getID(v[i-1]);
            update(idx, 1);
            cout << i - query(idx) + 1 << '\n';
        }
    }
    return 0;
}
分享本文 Share with friends