Fenwick Tree (Binary Indexed Tree)

Fenwick Tree (หรือ BIT) เป็นโครงสร้างข้อมูลที่รองรับ:

• Point update: $O(\log n)$
• Prefix sum query: $O(\log n)$

แนวคิด

ใช้ binary representation ของ indices เก็บ partial sums:

• tree[i] เก็บ sum ของ elements ใน range ที่กำหนดโดย least significant bit ของ $i$

Implementation

Basic BIT

class BIT {
    vector<long long> tree;
    int n;
    
public:
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    // Add val to index i (1-indexed)
    void update(int i, long long val) {
        for (; i <= n; i += i & (-i)) {
            tree[i] += val;
        }
    }
    
    // Sum of [1, i]
    long long query(int i) {
        long long sum = 0;
        for (; i > 0; i -= i & (-i)) {
            sum += tree[i];
        }
        return sum;
    }
    
    // Sum of [l, r]
    long long query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

BIT จาก Array

BIT(vector<long long>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
    for (int i = 1; i <= n; i++) {
        tree[i] += arr[i - 1];
        int j = i + (i & (-i));
        if (j <= n) tree[j] += tree[i];
    }
}

Operations

Point Update + Range Query

// Standard BIT as shown above
void update(int i, long long delta);
long long query(int l, int r);

Range Update + Point Query

ใช้ difference array concept:

class BITRangeUpdate {
    BIT bit;
    
public:
    BITRangeUpdate(int n) : bit(n) {}
    
    // Add val to [l, r]
    void update(int l, int r, long long val) {
        bit.update(l, val);
        bit.update(r + 1, -val);
    }
    
    // Get value at index i
    long long query(int i) {
        return bit.query(i);
    }
};

Range Update + Range Query

ใช้ 2 BITs:

class BITRangeRange {
    BIT bit1, bit2;
    int n;
    
public:
    BITRangeRange(int n) : n(n), bit1(n), bit2(n) {}
    
    // Add val to [l, r]
    void update(int l, int r, long long val) {
        bit1.update(l, val);
        bit1.update(r + 1, -val);
        bit2.update(l, val * (l - 1));
        bit2.update(r + 1, -val * r);
    }
    
    // Prefix sum [1, i]
    long long prefixSum(int i) {
        return bit1.query(i) * i - bit2.query(i);
    }
    
    // Sum of [l, r]
    long long query(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
};

2D BIT

class BIT2D {
    vector<vector<long long>> tree;
    int n, m;
    
public:
    BIT2D(int n, int m) : n(n), m(m), tree(n + 1, vector<long long>(m + 1, 0)) {}
    
    void update(int x, int y, long long val) {
        for (int i = x; i <= n; i += i & (-i)) {
            for (int j = y; j <= m; j += j & (-j)) {
                tree[i][j] += val;
            }
        }
    }
    
    // Sum of rectangle [1,1] to [x,y]
    long long query(int x, int y) {
        long long sum = 0;
        for (int i = x; i > 0; i -= i & (-i)) {
            for (int j = y; j > 0; j -= j & (-j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    // Sum of rectangle [x1,y1] to [x2,y2]
    long long query(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2) 
             - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

Applications

1. Inversion Count

นับจำนวน pairs $(i, j)$ ที่ $i < j$ และ $a[i] > a[j]$

long long inversionCount(vector<int>& arr) {
    int n = arr.size();
    int maxVal = *max_element(arr.begin(), arr.end());
    
    BIT bit(maxVal);
    long long count = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        count += bit.query(arr[i] - 1);  // Count smaller elements to the right
        bit.update(arr[i], 1);
    }
    
    return count;
}

2. K-th Smallest Element

int kthSmallest(BIT& bit, int n, int k) {
    int lo = 1, hi = n;
    
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (bit.query(mid) >= k) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    return lo;
}

3. Rectangle Sum Queries (with updates)

// Use 2D BIT

4. Order Statistics

เก็บ frequency ของแต่ละค่า ใช้ binary search หา k-th element

BIT vs Segment Tree

Aspect	BIT	Segment Tree
Space	$O(n)$	$O(4n)$
Constants	Very small	Larger
Operations	Sum, XOR, GCD	Any associative
Range update	Limited	Full support
Implementation	Simple	Complex

Complexity

Operation	Time
Build	$O(n)$
Update	$O(\log n)$
Query	$O(\log n)$
2D Update	$O(\log n \cdot \log m)$
2D Query	$O(\log n \cdot \log m)$

Tips

1. 1-indexed - BIT ทำงานกับ 1-indexed arrays
2. i & (-i) คือ lowest set bit ของ $i$
3. Build from array ทำได้ใน $O(n)$ ด้วย technique ข้างต้น
4. Coordinate compression - ถ้าค่ามีช่วงกว้างแต่จำนวนน้อย