Pada Chapter hashing/array dasar, kita membangun Fenwick tree (Binary Indexed Tree) untuk prefix sum dengan point update. Sekarang kita melangkah lebih jauh: 2D Fenwick tree untuk prefix sum matriks, dan range-update + range-query dengan dua BIT yang saling melengkapi. Fenwick unggul dari segment tree dalam hal konstanta kecil, memori O(n) (vs 4n), dan kode yang sangat ringkas. Untuk operasi yang ** hanya** butuh prefix query dan point update, Fenwick adalah pilihan terbaik. Untuk range update + range query, dua BIT trik menghasilkan O(log n) tanpa kompleksitas lazy propagation.

Aturan: Operasi yang Didukung Fenwick #

Fenwick tree asli mendukung:

  • add(idx, val): tambah val ke arr[idx], O(log n).
  • prefix(idx): jumlah arr[0..idx], O(log n).
  • range(l, r) = prefix(r) - prefix(l-1), O(log n).

Dibutuhkan hanya prefix-query-friendly operations (operator asosiatif + identitas, sama seperti segment tree). Fenwick tidak mendukung min/max dengan range update secara elegan — segment tree lazy diperlukan untuk itu.

Mekanisme: LSB dan Tree Implicit #

Fenwick memanfaatkan representasi biner indeks. Misal idx = 12 = 0b1100. LSB (least significant bit) = 0b0100 = 4. idx - LSB = 8. Artinya prefix(12) mencakup range [8, 11] (4 elemen) plus prefix(7). Secara rekursif, prefix(12) = bit_[12] + prefix(8 - 1) = bit_[12] + bit_[8] + prefix(7). Setiap bit_[idx] menyimpan sum dari arr[idx - LSB + 1 .. idx].

Operasi add dan prefix keduanya melibatkan rantai LSB yang panjangnya O(log n).

Implementasi Fenwick 1D, Range-Update, dan 2D #

cpp 
#include <iostream>
#include <vector>

class Fenwick {
public:
    explicit Fenwick(int n) : n_(n), bit_(n + 1, 0) {}
    void add(int idx, long long val) {
        for (++idx; idx <= n_; idx += idx & (-idx)) bit_[idx] += val;
    }
    long long prefix(int idx) const {
        long long s = 0;
        for (++idx; idx > 0; idx -= idx & (-idx)) s += bit_[idx];
        return s;
    }
    long long range(int l, int r) const { return prefix(r) - prefix(l - 1); }
private:
    int n_;
    std::vector<long long> bit_;
};

// Range update + range query via two BITs (all 1-based internally)
class RangeFenwick {
public:
    explicit RangeFenwick(int n) : n_(n), b1_(n + 2, 0), b2_(n + 2, 0) {}
    // l, r are 0-based; convert to 1-based internally
    void range_add(int l, int r, long long val) {
        ++l; ++r;
        add_internal(b1_, l, val);
        add_internal(b1_, r + 1, -val);
        add_internal(b2_, l, val * (l - 1));
        add_internal(b2_, r + 1, -val * r);
    }
    long long prefix_sum(int idx) const {
        ++idx;
        return sum_internal(b1_, idx) * idx - sum_internal(b2_, idx);
    }
    long long range_sum(int l, int r) const {
        return prefix_sum(r) - prefix_sum(l - 1);
    }
private:
    int n_;
    std::vector<long long> b1_, b2_;
    static void add_internal(std::vector<long long>& bit, int idx, long long val) {
        for (; idx < (int)bit.size(); idx += idx & (-idx)) bit[idx] += val;
    }
    static long long sum_internal(const std::vector<long long>& bit, int idx) {
        long long s = 0;
        for (; idx > 0; idx -= idx & (-idx)) s += bit[idx];
        return s;
    }
};

class Fenwick2D {
public:
    Fenwick2D(int r, int c) : R_(r), C_(c), bit_(r + 1, std::vector<long long>(c + 1, 0)) {}
    void add(int r, int c, long long val) {
        for (int i = r + 1; i <= R_; i += i & (-i))
            for (int j = c + 1; j <= C_; j += j & (-j))
                bit_[i][j] += val;
    }
    long long prefix(int r, int c) const {
        long long s = 0;
        for (int i = r + 1; i > 0; i -= i & (-i))
            for (int j = c + 1; j > 0; j -= j & (-j))
                s += bit_[i][j];
        return s;
    }
    long long range(int r1, int c1, int r2, int c2) const {
        return prefix(r2, c2) - prefix(r1 - 1, c2) - prefix(r2, c1 - 1) + prefix(r1 - 1, c1 - 1);
    }
private:
    int R_, C_;
    std::vector<std::vector<long long>> bit_;
};

int main() {
    Fenwick f(8);
    int vals[] = {3, 1, 4, 1, 5, 9, 2, 6};
    for (int i = 0; i < 8; ++i) f.add(i, vals[i]);
    std::cout << "Fenwick 1D prefix[5] = " << f.prefix(5) << '\n';
    std::cout << "Fenwick 1D range[2,5] = " << f.range(2, 5) << '\n';

    RangeFenwick rf(8);
    rf.range_add(2, 5, 10);
    std::cout << "\nRangeFenwick setelah add(2,5,10):\n";
    std::cout << "  range[2,5] = " << rf.range_sum(2, 5) << '\n';
    std::cout << "  range[0,7] = " << rf.range_sum(0, 7) << '\n';
    rf.range_add(0, 3, 100);
    std::cout << "setelah add(0,3,100):\n";
    std::cout << "  range[0,7] = " << rf.range_sum(0, 7) << '\n';
    std::cout << "  range[4,5] = " << rf.range_sum(4, 5) << '\n';

    Fenwick2D f2(3, 3);
    f2.add(0, 0, 1); f2.add(0, 1, 2); f2.add(0, 2, 3);
    f2.add(1, 0, 4); f2.add(1, 1, 5); f2.add(1, 2, 6);
    f2.add(2, 0, 7); f2.add(2, 1, 8); f2.add(2, 2, 9);
    std::cout << "\nFenwick 2D prefix[1,1] = " << f2.prefix(1, 1) << '\n';
    std::cout << "Fenwick 2D range[0,0]-[2,2] = " << f2.range(0, 0, 2, 2) << '\n';
    std::cout << "Fenwick 2D range[1,1]-[2,2] = " << f2.range(1, 1, 2, 2) << '\n';
    return 0;
}

Output yang Dihasilkan:

text 
Fenwick 1D prefix[5] = 23
Fenwick 1D range[2,5] = 19

RangeFenwick setelah add(2,5,10):
  range[2,5] = 40
  range[0,7] = 40
setelah add(0,3,100):
  range[0,7] = 440
  range[4,5] = 20

Fenwick 2D prefix[1,1] = 12
Fenwick 2D range[0,0]-[2,2] = 45
Fenwick 2D range[1,1]-[2,2] = 28

Bedah Kode Baris-per-Baris #

  1. for (++idx; idx <= n_; idx += idx & (-idx)) pada add: konversi 0-based ke 1-based (++idx). LSB didapat dengan idx & (-idx) — ini trik bitwise standar. Iterasi menaik sambil menambahkan val ke setiap node yang cover idx. Contoh: add(0, val) menambah bit_[1], bit_[2], bit_[4], bit_[8], dst. — semua node yang cover index 0.
  2. for (++idx; idx > 0; idx -= idx & (-idx)) pada prefix: iterasi menurun sambil menjumlahkan node-node yang membentuk prefix. Contoh: prefix(12) menjumlahkan bit_[12], bit_[8], bit_[0] (tidak ada). Tiga iterasi = O(log n).
  3. range(l, r) = prefix(r) - prefix(l-1): trik standar prefix-sum untuk dapat range sum.
  4. RangeFenwick dengan dua BIT: trik untuk range-update + range-query. Setelah range_add(l, r, val), prefix sum baru prefix(idx) untuk idx ∈ [l, r] naik sebesar val * (idx - l + 1) = val * idx - val * (l - 1). Untuk idx > r, naik val * (r - l + 1) konstan. Dua BIT b1_ (koefisien val * idx) dan b2_ (intercept -val * (l-1) atau -val * r) memodelkan fungsi piecewise-linear ini.
  5. add_internal(b1_, l, val); add_internal(b1_, r+1, -val): membentuk fungsi step — b1 bernilai val di [l, r], 0 di tempat lain. Multiply dengan idx saat query → val * (idx - l + 1) untuk idx ∈ [l, r].
  6. add_internal(b2_, l, val * (l-1)); add_internal(b2_, r+1, -val * r): koreksi intercept. Formula akhir prefix(idx) = sum_internal(b1, idx) * idx - sum_internal(b2, idx).
  7. Fenwick2D: extend ke 2D dengan nested loop. Setiap node bit_[i][j] menyimpan sum dari rectangle [i - LSB(i) + 1, j - LSB(j) + 1] hingga [i, j]. Kompleksitas O(log R × log C) per operasi.
  8. range(r1, c1, r2, c2): inclusion-exclusion standar 2D prefix sum.
  9. Verifikasi:
    • 1D: prefix[5] = 3+1+4+1+5+9 = 23, range[2,5] = 4+1+5+9 = 19. ✓
    • RangeFenwick: setelah add(2,5,10), arr = [0,0,10,10,10,10,0,0]. range[2,5] = 40, range[0,7] = 40. Setelah add(0,3,100), arr = [100,100,110,110,10,10,0,0]. range[0,7] = 440, range[4,5] = 20. ✓
    • 2D: matriks [[1,2,3],[4,5,6],[7,8,9]]. prefix[1,1] = 1+2+4+5 = 12. range[0,0]-[2,2] = 45. range[1,1]-[2,2] = 5+6+8+9 = 28. ✓

Kompleksitas dan Perbandingan #

StrukturPoint updateRange queryRange updateMemori
Fenwick 1DO(log n)O(log n)—n+1
RangeFenwick (2 BIT)—O(log n)O(log n)2n
Fenwick 2DO(log R·log C)O(log R·log C)—R×C
Segment tree lazyO(log n)O(log n)O(log n)8n

Ringkasan #

  • Fenwick tree memakai representasi biner index dan operasi LSB idx & (-idx).
  • 1D: add dan prefix keduanya O(log n), memori O(n).
  • RangeFenwick dengan dua BIT mendukung range-update + range-query untuk sum, O(log n).
  • Fenwick 2D: nested BIT untuk prefix sum matriks, O(log R · log C) per operasi.
  • Selalu 1-based internal. idx = 0 adalah infinite loop jebakan.
  • Fenwick unggul untuk prefix-query-friendly operations (sum, XOR). Untuk min/max dengan update, segment tree lebih fleksibel.
  • Trade-off vs segment tree: Fenwick kode lebih pendek, konstanta ~2× lebih kecil, memori setengah. Segment tree lebih fleksibel untuk operasi kompleks (lazy, persistent, merge-sort).