Fenwick Tree

Fenwick Tree atau Binary Indexed Tree (BIT) adalah struktur data elegan yang menjawab dua pertanyaan dalam O(log n): “berapa prefix sum A[0..k]?” dan “update A[i] += delta”. Dibanding segment tree, Fenwick tree memerlukan memori lebih sedikit (cukup n+1 elemen, vs 4n), kode lebih pendek, dan konstanta lebih kecil. Trik intinya: tree[i] menyimpan jumlah elemen pada rentang (i - lowbit(i), i] di mana lowbit(i) = i & -i adalah bit terendah yang aktif. Pada Chapter ini kita akan membedah mengapa trik i & -i bekerja, mengimplementasikan add dan prefix_sum, dan menggunakannya untuk menyelesaikan soal klasik Inversion Count.

Trik lowbit: i & -i #

Operasi i & -i mengisolasi bit terendah yang aktif dalam representasi biner i. Contoh:

i = 12 (binary 1100)
-i = -12 (two's complement: 10100)
i & -i = 1100 & 10100 = 0100 = 4

lowbit(12) = 4

Mengapa ini bekerja? Two’s complement membalik semua bit lalu tambah 1. Bit terendah aktif i tetap aktif setelah pembalikan (karena bit di bawahnya 0), sehingga AND dengan i mengisolasi bit tersebut.

Beberapa contoh:

Struktur Fenwick Tree #

tree[i] menyimpan jumlah elemen pada rentang (i - lowbit(i), i] (1-indexed). Untuk i = 6 (lowbit 2), tree[6] = A[5] + A[6]. Untuk i = 8 (lowbit 8), tree[8] = A[1] + A[2] + ... + A[8].

Setiap tree[i] mencakup rentang dengan panjang lowbit(i). Untuk prefix_sum(7) = tree[7] + tree[6] + tree[4] = A[7] + (A[5]+A[6]) + (A[1]+A[2]+A[3]+A[4]).

Operasi prefix_sum dan add #

prefix_sum(k) — jumlah A[1..k] #

Mulai dari i = k, tambahkan tree[i], lalu i -= lowbit(i). Ulangi sampai i = 0.

add(idx, delta) — A[idx] += delta #

Mulai dari i = idx, tambahkan delta ke tree[i], lalu i += lowbit(i). Ulangi sampai i > n.

#include <iostream>
#include <vector>

class FenwickTree {
public:
    explicit FenwickTree(int n) : n_(n), tree_(n + 1, 0) {}

    // Tambahkan delta ke A[idx] (1-indexed)
    void add(int idx, int delta) {
        for (; idx <= n_; idx += idx & -idx) {
            tree_[idx] += delta;
        }
    }

    // Prefix sum A[1..k] (1-indexed)
    int prefix_sum(int k) const {
        int s = 0;
        for (; k > 0; k -= k & -k) {
            s += tree_[k];
        }
        return s;
    }

    // Range sum A[l..r] (1-indexed, inclusive)
    int range_sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l - 1);
    }

private:
    int n_;
    std::vector<int> tree_;
};

int main() {
    // Bangun dari array A = [3, 1, 4, 1, 5, 9, 2, 6] (1-indexed)
    std::vector<int> A = {0, 3, 1, 4, 1, 5, 9, 2, 6};  // dummy 0 di index 0
    FenwickTree ft(8);
    for (int i = 1; i <= 8; ++i) ft.add(i, A[i]);

    std::cout << "Prefix sum A[1..1] = " << ft.prefix_sum(1) << '\n';
    std::cout << "Prefix sum A[1..3] = " << ft.prefix_sum(3) << '\n';
    std::cout << "Prefix sum A[1..8] = " << ft.prefix_sum(8) << '\n';
    std::cout << "Range sum A[3..6]  = " << ft.range_sum(3, 6) << '\n';

    // Update: A[4] += 10
    ft.add(4, 10);
    std::cout << "\nSetelah A[4] += 10:\n";
    std::cout << "Prefix sum A[1..8] = " << ft.prefix_sum(8) << '\n';
    std::cout << "Range sum A[3..6]  = " << ft.range_sum(3, 6) << '\n';
    return 0;
}

Output yang Dihasilkan:

Prefix sum A[1..1] = 3
Prefix sum A[1..3] = 8
Range sum A[3..6]  = 19

Setelah A[4] += 10:
Prefix sum A[1..8] = 41
Range sum A[3..6]  = 29

1. add(idx, delta): loop idx += idx & -idx (langkah ke parent berikutnya yang mencakup idx). Setiap node yang mencakup idx diupdate dengan delta. Jumlah iterasi = jumlah bit aktif dalam idx ≤ log₂ n.
2. prefix_sum(k): loop k -= k & -k (langkah ke subtree terbesar yang tidak mencakup k — yang ujungnya tepat sebelum k). Jumlah iterasi ≤ log₂ n.
3. range_sum(l, r) = prefix_sum(r) - prefix_sum(l-1): sifat aljabar prefix sum. Hanya butuh 2 × O(log n) per query.
4. Verifikasi A[1..8] awal: 3+1+4+1+5+9+2+6 = 31. Output tidak menampilkan ini tapi prefix_sum(8) = 31 sebelum update.
5. Setelah A[4] += 10: A[1..8] baru = 31 + 10 = 41. A[3..6] = 4+1+5+9 = 19, setelah update = 19 + 10 = 29.

Verifikasi Invariant: Bagaimana Trik Bekerja #

Pada Fenwick tree, tree[i] mencakup rentang [i - lowbit(i) + 1, i]. Misal i = 6, lowbit = 2, sehingga rentang [5, 6]. Saat add(5, delta):

• i = 5 (lowbit 1), update tree[5] (rentang [5, 5]).
• i = 6 (lowbit 2), update tree[6] (rentang [5, 6]).
• i = 8 (lowbit 8), update tree[8] (rentang [1, 8]).
• i = 16 > n, stop.

Tiga node diupdate — semua node yang mencakup idx = 5. Pola i += lowbit(i) menemukan parent berikutnya yang mencakup idx.

Saat prefix_sum(7):

• i = 7 (lowbit 1), add tree[7] (rentang [7, 7]).
• i = 6 (lowbit 2), add tree[6] (rentang [5, 6]).
• i = 4 (lowbit 4), add tree[4] (rentang [1, 4]).
• i = 0, stop.

Total = A[7] + (A[5]+A[6]) + (A[1]+A[2]+A[3]+A[4]) = A[1..7]. Benar.

Aplikasi: Menghitung Inversion Count #

Inversion count: pasangan (i, j) dengan i < j dan A[i] > A[j]. Naif O(n²); dengan Fenwick tree O(n log n).

#include <iostream>
#include <vector>
#include <algorithm>

long long inversion_count(std::vector<int>& A) {
    int n = A.size();
    // Coordinate compression: map nilai ke rank 1..n
    std::vector<int> sorted = A;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    auto rank_of = [&](int v) {
        return (int)(std::lower_bound(sorted.begin(), sorted.end(), v) - sorted.begin()) + 1;
    };

    int m = sorted.size();
    std::vector<int> tree(m + 1, 0);
    auto add = [&](int idx, int delta) {
        for (; idx <= m; idx += idx & -idx) tree[idx] += delta;
    };
    auto prefix = [&](int k) {
        int s = 0;
        for (; k > 0; k -= k & -k) s += tree[k];
        return s;
    };

    long long inv = 0;
    // Proses dari kanan ke kiri
    for (int i = n - 1; i >= 0; --i) {
        int r = rank_of(A[i]);
        // Hitung elemen di kanan i dengan nilai lebih kecil dari A[i] (inversion)
        int smaller = prefix(r - 1);
        inv += smaller;
        add(r, 1);
    }
    return inv;
}

int main() {
    std::vector<int> A = {5, 2, 6, 1};
    std::cout << "Inversion count [5,2,6,1] = " << inversion_count(A) << '\n';

    std::vector<int> B = {1, 2, 3, 4, 5};
    std::cout << "Inversion count [1..5]    = " << inversion_count(B) << '\n';

    std::vector<int> C = {5, 4, 3, 2, 1};
    std::cout << "Inversion count [5..1]    = " << inversion_count(C) << '\n';
    return 0;
}

Output yang Dihasilkan:

Inversion count [5,2,6,1] = 4
Inversion count [1..5]    = 0
Inversion count [5..1]    = 10

1. Coordinate compression: nilai array dipetakan ke rank [1..m] di mana m adalah jumlah nilai unik. Penting agar Fenwick tree hanya butuh ukuran m, bukan max_value (yang bisa 1 miliar).
2. Loop kanan→kiri: untuk setiap A[i], hitung berapa elemen di kanan i dengan nilai lebih kecil — itulah inversion (i<j dan A[i] > A[j]).
3. smaller = prefix(r - 1): jumlah elemen yang sudah dimasukkan ke Fenwick tree (= elemen di kanan i) dengan rank < r (nilai lebih kecil). Inversion terjadi karena A[i] lebih besar dari elemen-elemen tersebut.
4. add(r, 1): catat bahwa elemen dengan rank r sekarang ada di tree.
5. [5,2,6,1] = 4 inversion: pasangan (5,2), (5,1), (2,1), (6,1). Sesuai perhitungan manual.
6. [1..5] = 0: array terurut ascending → tidak ada inversion.
7. [5..1] = 10: setiap pasangan adalah inversion. C(5,2) = 5×4/2 = 10.

Fenwick vs Segment Tree #

Ringkasan #

• Fenwick Tree (BIT): struktur data untuk prefix sum O(log n) dan point update O(log n).
• Trik inti: i += i & -i (naik ke parent) dan i -= i & -i (turun ke ancestor). lowbit(i) = i & -i mengisolasi bit terendah yang aktif.
• tree[i] menyimpan rentang [i - lowbit(i) + 1, i] (1-indexed).
• Tiga operasi: add(idx, delta) O(log n), prefix_sum(k) O(log n), range_sum(l, r) = prefix_sum(r) - prefix_sum(l-1).
• Memori sangat efisien: hanya n+1 elemen vs segment tree 4n.
• Aplikasi klasik: inversion count O(n log n), dynamic prefix sum, frequency counting.
• Tidak mendukung min/max secara langsung — segment tree lebih fleksibel untuk aggregate non-invertible.