Fenwick Tree (Binary Indexed Tree)

Fenwick Tree (hay Binary Indexed Tree — BIT) là cấu trúc dữ liệu cho phép vừa cập nhật một phần tử, vừa tính tổng tiền tố (prefix sum) của mảng, mỗi thao tác chỉ tốn $O(\log N)$. So với mảng tổng tiền tố tĩnh — truy vấn $O(1)$ nhưng mỗi lần cập nhật phải dựng lại trong $O(N)$ — và so với cách ngây thơ tính tổng đoạn trong $O(N)$, Fenwick Tree đưa cả hai thao tác về $O(\log N)$. Bài toán điển hình: cho mảng $a[1..N]$, xử lý xen kẽ hai loại truy vấn "cộng $v$ vào $a[i]$" và "tính $a[l]+\dots +a[r]$".

So với Segment Tree (xem Segment Tree), Fenwick Tree code ngắn hơn nhiều, hằng số nhỏ và chỉ tốn $O(N)$ bộ nhớ; đổi lại nó chỉ xử lý gọn các phép có nghịch đảo (tổng, đếm) chứ không trực tiếp làm min/max.

Ý tưởng / Trực giác

Mấu chốt nằm ở biểu diễn nhị phân của chỉ số. Ta xây một mảng $\text{tree}[1..N]$, trong đó $\text{tree}[i]$ không lưu $a[i]$ mà lưu tổng của một đoạn con kết thúc tại $i$:

$$\text{tree}[i]=a[i-\text{lowbit}(i)+1]+\dots +a[i]$$

với $\text{lowbit}(i)=i<mrow><mi>\&</mi></mrow>(-i)$ là bit 1 thấp nhất của $i$. Nói cách khác, $\text{tree}[i]$ phụ trách một đoạn có độ dài đúng bằng $\text{lowbit}(i)$.

Vì sao điều này giúp tính prefix sum nhanh? Mọi số nguyên dương $i$ đều phân tích được thành tổng các luỹ thừa của 2 (các bit 1 trong biểu diễn nhị phân). Tương ứng, đoạn $[1..i]$ tách được thành một số ít đoạn con rời nhau mà mỗi đoạn chính là một ô $\text{tree}$. Ta đi từ $i$, cộng $\text{tree}[i]$, rồi nhảy về $i-\text{lowbit}(i)$ (xoá bit 1 thấp nhất) và lặp lại cho đến khi về 0. Số bit 1 của $i$ tối đa là ${\log }_{2}N$, nên prefix sum chỉ tốn $O(\log N)$.

Tại sao $\text{lowbit}(i)=i<mrow><mi>\&</mi></mrow>(-i)$? Trong bù 2, $-i$ là phần bù của $i$ cộng 1, nên $-i$ đảo mọi bit phía trên bit 1 thấp nhất và giữ nguyên bit đó; phép AND giữ lại đúng bit 1 thấp nhất. Ví dụ $i=12={1100}_2$ thì $\text{lowbit}={100}_2=4$.

Khi cập nhật $a[i]$ thêm $\delta$, ta phải cộng $\delta$ vào mọi ô $\text{tree}$ mà đoạn của nó chứa $i$. Các ô đó lập thành chuỗi $i\to i+\text{lowbit}(i)\to \dots$ (cộng dồn bit thấp nhất), cũng tối đa $\log N$ bước. Hai phép "đi xuống để hỏi" (trừ lowbit) và "đi lên để sửa" (cộng lowbit) đối xứng nhau — đó chính là vẻ đẹp của Fenwick Tree.

Ví dụ chạy tay

Xét mảng $a=[3,2,5,1,4,6,2,7]$ ($N=8$), chỉ số từ 1. Mỗi $\text{tree}[i]$ phụ trách đoạn dài $\text{lowbit}(i)$:

 i :   1    2    3    4    5    6    7    8
a[i]:  3    2    5    1    4    6    2    7
lowbit: 1   2    1    4    1    2    1    8
phụ trách đoạn:
 tree[1] = a[1]            = 3            (đoạn [1,1], dài 1)
 tree[2] = a[1..2]         = 3+2     = 5  (đoạn [1,2], dài 2)
 tree[3] = a[3]            = 5            (đoạn [3,3], dài 1)
 tree[4] = a[1..4]         = 3+2+5+1 = 11 (đoạn [1,4], dài 4)
 tree[5] = a[5]            = 4            (đoạn [5,5], dài 1)
 tree[6] = a[5..6]         = 4+6     = 10 (đoạn [5,6], dài 2)
 tree[7] = a[7]            = 2            (đoạn [7,7], dài 1)
 tree[8] = a[1..8]         = 30           (đoạn [1,8], dài 8)

Có thể hình dung phạm vi phủ của các ô như sau (mỗi = là một phần tử đoạn ô đó phủ):

index:  1   2   3   4   5   6   7   8
tree8:  =================================   [1..8]
tree4:  =================                    [1..4]
tree2:  =======                              [1..2]
tree6:                  =======              [5..6]
tree1:  ===                                  [1..1]
tree3:          ===                          [3..3]
tree5:                  ===                  [5..5]
tree7:                          ===          [7..7]

Truy vấn query(6) = tổng $a[1.\mathrm{.6}]$. Bắt đầu $i=6$, cộng dần rồi xoá lowbit:

i = 6 = 110b   -> cộng tree[6] = 10,   nhảy về 6 - lowbit(6)=6-2 = 4
i = 4 = 100b   -> cộng tree[4] = 11,   nhảy về 4 - lowbit(4)=4-4 = 0
i = 0          -> dừng
tổng = 10 + 11 = 21

Kiểm chứng: $a[1.\mathrm{.6}]=3+2+5+1+4+6=21$. Đúng. Chỉ cần 2 bước thay vì 6.

Cập nhật update(3, +4) (cộng 4 vào $a[3]$). Bắt đầu $i=3$, cộng dần rồi thêm lowbit:

i = 3 = 011b   -> tree[3] += 4   (đoạn [3,3] chứa 3),   nhảy về 3 + lowbit(3)=3+1 = 4
i = 4 = 100b   -> tree[4] += 4   (đoạn [1,4] chứa 3),   nhảy về 4 + lowbit(4)=4+4 = 8
i = 8 =1000b   -> tree[8] += 4   (đoạn [1,8] chứa 3),   nhảy về 8 + 8 = 16 > N
dừng

Các ô $\text{tree}[1],\text{tree}[2]$ (đoạn không chứa chỉ số 3) không bị động đến — đúng như mong đợi.

Cài đặt

Fenwick Tree cơ bản (cập nhật điểm, truy vấn prefix)

struct BIT {
    int n;
    vector<long long> tree;              // dùng long long để tránh tràn số
    BIT(int n) : n(n), tree(n + 1, 0) {} // chỉ số chạy từ 1..n

    // Cộng delta vào a[i]: leo lên theo i += lowbit(i)
    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i))
            tree[i] += delta;
    }

    // Tổng tiền tố a[1..i]: tụt xuống theo i -= lowbit(i)
    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }

    // Tổng đoạn [l, r] = prefix(r) - prefix(l-1)
    long long query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

Dựng BIT từ mảng có sẵn trong $O(N)$ thay vì gọi $N$ lần update ($O(N\log N)$):

// Sau khi đã đặt tree[i] = a[i] cho mọi i:
for (int i = 1; i <= n; i++) {
    int j = i + (i & (-i));
    if (j <= n) tree[j] += tree[i];      // đẩy tổng lên ô cha
}

Bản Python tương đương:

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):          # tổng a[1..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)

Ứng dụng kinh điển: đếm nghịch thế

Nghịch thế là cặp $(i,j)$ với $i<j$ và $a_i>a_j$. Quét trái sang phải, với mỗi $a_j$ đếm xem có bao nhiêu phần tử đã chèn lớn hơn nó — đó chính là số nghịch thế kết thúc tại $j$. Dùng BIT trên trục giá trị (nén toạ độ nếu giá trị lớn):

// Giả sử a[] đã nén về 1..M (M giá trị phân biệt)
long long countInversions(vector<int>& a, int M) {
    BIT bit(M);
    long long inv = 0;
    for (int x : a) {
        // số phần tử đã chèn có giá trị > x  =  (đã chèn) - (số <= x)
        inv += bit.query(M) - bit.query(x);
        bit.update(x, 1);                 // đánh dấu giá trị x xuất hiện
    }
    return inv;
}

Độ phức tạp

Với $Q$ truy vấn, tổng thời gian là $O((N+Q)\log N)$.

⚠️ Lỗi thường gặp

• Đánh chỉ số từ 0. Fenwick Tree bắt buộc chỉ số bắt đầu từ 1, vì $\text{lowbit}(0)=0$ khiến vòng update lặp vô hạn (chỉ số không bao giờ tăng) và vòng query dừng ngay. Nếu dữ liệu gốc từ 0, hãy cộng 1 vào mọi chỉ số.
• Tràn số (overflow). Tổng nhiều giá trị lớn dễ vượt int (ví dụ $N={10}^5$ phần tử cỡ ${10}^8$ cho tổng $~{10}^{13}$). Luôn dùng long long cho mảng tree và biến tích luỹ. Khi đếm nghịch thế, số cặp có thể tới $\left(\genfrac{}{}{0ex}{}{N}{2}\right)\approx 5\times {10}^9$ — vượt int.
• Quên nén toạ độ (coordinate compression). Khi BIT chạy trên trục giá trị mà giá trị lên tới ${10}^9$, không thể cấp mảng kích thước đó. Phải nén về $1..M$ trước (sort + unique + tra cứu). Quên bước này gây tràn bộ nhớ hoặc lỗi truy cập.
• Sai biên với query(l-1). Tổng đoạn dùng query(r) - query(l-1). Khi $l=1$ thì $l-1=0$ và query(0) phải trả về 0 (vòng for không chạy vì $i>0$ sai ngay) — cài đúng thì an toàn, nhưng nếu vô tình truy cập tree[0] sẽ sai.
• Modulo âm. Khi bài yêu cầu in theo modulo và phép tính có trừ (ví dụ query(r) - query(l-1) rồi % MOD), kết quả có thể âm. Sửa: ((x % MOD) + MOD) % MOD. Lưu ý $\text{lowbit}$ và cấu trúc BIT bản thân không liên quan modulo — chỉ giá trị lưu mới cần.
• Cập nhật giá trị tuyệt đối thay vì delta. update(i, x) cộng $x$ chứ không gán $a[i]=x$. Muốn gán giá trị mới $v$, phải truyền update(i, v - a[i]) và nhớ cập nhật lại $a[i]$.

Biến thể / Mở rộng

Cập nhật đoạn + truy vấn đoạn (hai BIT)

Dùng hai BIT kết hợp difference array để vừa cộng $v$ vào cả đoạn $[l,r]$ vừa truy vấn tổng đoạn, tất cả $O(\log N)$:

$$\text{prefix}(i)=B_1.\text{query}(i)·i-B_2.\text{query}(i)$$

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

    // Cộng v vào mọi 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);
    }
};

Fenwick Tree 2 chiều

Cập nhật điểm $(x,y)$ và truy vấn tổng hình chữ nhật góc $(1,1)$–$(x,y)$ trong $O(\log N\log M)$:

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] x [y1..y2] (nguyên lý bù trừ)
    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

Bài tập luyện

• Nghịch Thế Cửa Sổ Trượt (swinv) — (Advanced) Đếm nghịch thế trong từng cửa sổ trượt độ dài $k$; luyện BIT trên trục giá trị (có nén toạ độ) kết hợp thêm/bớt phần tử khi cửa sổ trượt.
• Ảnh cân bằng (bphoto) — (Advanced) Với mỗi phần tử đếm số phần tử lớn hơn ở bên trái và bên phải; áp dụng BIT đếm trực tiếp theo hai lượt quét.
• Cắt tóc (haircut20) — (Advanced) Đếm số nghịch thế khi cắt ngưỡng giá trị tăng dần; rèn cách dùng đóng góp nghịch thế tích luỹ bằng BIT.
• Kệ Thuốc Phép (matchstk) — (Advanced) Quy về số phép đổi chỗ liền kề tối thiểu = số nghịch thế của hoán vị, tính bằng BIT rồi lấy modulo (cẩn thận tràn số và modulo).
• Nhảy Ô — Gold (hopscotchgo) — (Veteran) Kết hợp quy hoạch động với BIT để cộng dồn theo điều kiện thứ tự — bước tiến từ BIT thuần sang BIT làm tăng tốc DP.
• Cắt Cỏ (mowing16) — (Expert) BIT/Segment Tree kết hợp sweep line trên các sự kiện; bài tổng hợp nâng cao để củng cố BIT trong cấu trúc dữ liệu phức tạp.