Fenwick Tree (Binary Indexed Tree)

Wiki › Cấu trúc dữ liệu › Cây

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

Fenwick Tree (hay Binary Indexed Tree — BIT) là cấu trúc dữ liệu hỗ trợ prefix sum và cập nhật điểm trong $O (\log N)$ , với cài đặt đơn giản hơn Segment Tree.

Ý tưởng: Mỗi vị trí $i$ trong mảng BIT chịu trách nhiệm cho một đoạn có độ dài bằng i & (-i) (bit thấp nhất của $i$ ).

Cài đặt cơ bản

struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n) : n(n), tree(n+1, 0) {}

    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }

    long long query(int i) {  // prefix sum [1..i]
        long long s = 0;
        for (; i > 0; i -= i & (-i)) s += tree[i];
        return s;
    }

    long long query(int l, int r) { return query(r) - query(l-1); }
};

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

BIT hỗ trợ cập nhật và truy vấn đoạn

Dùng hai BIT để vừa cập nhật đoạn $[l, r]$ vừa truy vấn tổng đoạn — $O (\log N)$ :

sum [1 . . i] = B_{1} . query (i) \cdot i - B_{2} . query (i)

struct RangeBIT {
    int n;
    BIT b1, b2;
    RangeBIT(int n) : n(n), b1(n), b2(n) {}

    // Cộng v vào tất cả phần tử trong [l, r]
    void range_update(int l, int r, long long v) {
        b1.update(l, v);         b1.update(r+1, -v);
        b2.update(l, v*(l-1));   b2.update(r+1, -v*r);
    }

    long long prefix_sum(int i) {
        return b1.query(i) * i - b2.query(i);
    }

    long long range_sum(int l, int r) {
        return prefix_sum(r) - prefix_sum(l-1);
    }
};

BIT 2 chiều

Hỗ trợ cập nhật điểm $(x, y)$ và truy vấn tổng hình chữ nhật $[1 . . x] [1 . . y]$ :

struct BIT2D {
    int n, m;
    vector<vector<long long>> tree;
    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 delta) {
        for (int i = x; i <= n; i += i & (-i))
            for (int j = y; j <= m; j += j & (-j))
                tree[i][j] += delta;
    }

    long long query(int x, int y) {
        long long s = 0;
        for (int i = x; i > 0; i -= i & (-i))
            for (int j = y; j > 0; j -= j & (-j))
                s += tree[i][j];
        return s;
    }

    // Tổng hình chữ nhật [x1..x2][y1..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);
    }
};

So sánh với Segment Tree

	Segment Tree	Fenwick Tree
Cài đặt	Phức tạp hơn	Đơn giản hơn
Bộ nhớ	$O (4 N)$	$O (N)$
Hỗ trợ min/max	Có	Không trực tiếp
Lazy propagation	Có	Có (dùng 2 BIT)
2D	Có (phức tạp)	Có (đơn giản hơn)
Khi nào dùng	Cần min/max hoặc lazy phức tạp	Chỉ cần tổng/đếm

Bình luận

Không có bình luận tại thời điểm này.