Binary Indexed Tree (Fenwick Tree) ใน C++

เปรียบเทียบกับ Array ธรรมดา

หลักการทำงาน

ใช้ 1-based Array BIT[n+1] โดย:

• BIT[i] เก็บผลรวมของช่วง [i - LSB(i) + 1, i]
• LSB(i) = i & (-i) (Least Significant Bit - บิต 1 ตัวสุดท้าย)
• โครงสร้าง Tree Implicit ใน Array

Operations หลัก

1. Prefix Sum Query - sum(i)

int sum(int i) {
    int result = 0;
    while (i > 0) {
        result += BIT[i];
        i -= i & (-i);  // ลบ LSB -> โจมตี Parent
    }
    return result;
}

2. Point Update - add(i, delta)

void add(int i, int delta) {
    while (i <= n) {
        BIT[i] += delta;
        i += i & (-i);  // บวก LSB -> โจมตี Ancestors
    }
}

3. Range Sum Query - sum(l, r)

int rangeSum(int l, int r) {
    return sum(r) - sum(l - 1);
}

โค้ดตัวอย่างสมบูรณ์ (C++)

#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
    vector<int> BIT;
    int n;

public:
    FenwickTree(int size) : n(size), BIT(size + 1, 0) {}

    // Build from array in O(n log n) or O(n)
    FenwickTree(const vector<int>& arr) : n(arr.size()), BIT(n + 1, 0) {
        for (int i = 1; i <= n; i++) {
            BIT[i] += arr[i - 1];
            int j = i + (i & -i);
            if (j <= n) BIT[j] += BIT[i];
        }
    }

    void add(int i, int delta) {  // 1-based index
        for (; i <= n; i += i & -i)
            BIT[i] += delta;
    }

    int sum(int i) const {  // Prefix sum [1..i]
        int res = 0;
        for (; i > 0; i -= i & -i)
            res += BIT[i];
        return res;
    }

    int rangeSum(int l, int r) const {  // [l..r] 1-based
        return sum(r) - sum(l - 1);
    }

    // Optional: Point query (value at index i)
    int pointQuery(int i) const {
        return rangeSum(i, i);
    }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    FenwickTree ft(arr);

    cout << "Prefix sum [1..3]: " << ft.sum(3) << endl;      // 1+3+5=9
    cout << "Range sum [2..5]: " << ft.rangeSum(2, 5) << endl;  // 3+5+7+9=24

    ft.add(3, 10);  // arr[3] += 10 (5 -> 15)
    cout << "After add(3, 10):" << endl;
    cout << "Prefix sum [1..3]: " << ft.sum(3) << endl;      // 1+3+15=19
    cout << "Range sum [2..5]: " << ft.rangeSum(2, 5) << endl;  // 3+15+7+9=34

    return 0;
}

ผลลัพธ์

Prefix sum [1..3]: 9
Range sum [2..5]: 24
After add(3, 10):
Prefix sum [1..3]: 19
Range sum [2..5]: 34

คำอธิบายเพิ่มเติม

• 1-based Indexing สำคัญมาก - ต้องปรับ Index อย่างระมัดระวัง
• Build แบบ O(n) เร็วกว่า Add ทีละตัว O(n log n)
• ประยุกต์ได้: Range Update + Point Query (ใช้ BIT 2 ตัว), Range Update + Range Query
• ข้อดีเหนือ Segment Tree: โค้ดสั้น, ใช้หน่วยความจำน้อยกว่า, เร็วกว่าคงที่
• ข้อจำกัด: ไร้การรองรับ Range Min/Max Query ได้โดยตรง

Index:  1  2  3  4  5  6  7  8
Binary: 001 010 011 100 101 110 111 1000
LSB:    1   2   1   4   1   2   1   8
Covers: [1] [1-2] [3] [1-4] [5] [5-6] [7] [1-8]