PENALGO

Giao diện

Fenwick Tree (BIT) — Truy vấn tiền tố thanh lịch ​

Segment Tree giải quyết mọi bài toán range query, nhưng khi yêu cầu chỉ đơn giản là prefix sum + point update, bạn đang dùng dao mổ trâu để gọt bút chì. Fenwick Tree (hay Binary Indexed Tree) làm cùng việc với 1/4 lượng code, 1/4 bộ nhớ, và hằng số thời gian nhỏ hơn đáng kể.

Peter Fenwick công bố cấu trúc này năm 1994 với một insight tuyệt đẹp: biểu diễn nhị phân của index đã chứa sẵn thông tin về phạm vi quản lý của mỗi node. Không cần cây tường minh, không cần đệ quy — chỉ cần vài phép toán bit là đủ duyệt toàn bộ cấu trúc.

Bức tranh tư duy ​

Hình dung một hệ thống kế toán theo kiểu "sổ cái phân cấp". Thay vì mỗi trang sổ ghi một giao dịch, mỗi trang ghi tổng của một nhóm giao dịch — nhóm lớn hay nhỏ tùy thuộc vào vị trí trang trong sổ.

Index (1-based)  | Nhị phân | Lowbit | Phạm vi quản lý
-----------------+----------+--------+-----------------
1                | 0001     | 1      | [1, 1]
2                | 0010     | 2      | [1, 2]
3                | 0011     | 1      | [3, 3]
4                | 0100     | 4      | [1, 4]
5                | 0101     | 1      | [5, 5]
6                | 0110     | 2      | [5, 6]
7                | 0111     | 1      | [7, 7]
8                | 1000     | 8      | [1, 8]

Quy luật: lowbit(i) = i & (-i) cho biết node i quản lý bao nhiêu phần tử. Node 4 (nhị phân 0100) có lowbit = 4, quản lý 4 phần tử [1..4]. Node 6 (nhị phân 0110) có lowbit = 2, quản lý 2 phần tử [5..6].

Để tính prefix sum [1..7]: cộng tree[7] + tree[6] + tree[4] — mỗi bước bỏ lowbit khỏi index. Để update index 3: cập nhật tree[3], tree[4], tree[8] — mỗi bước cộng lowbit vào index. Cả hai đều chạy O(log n) bước.

Cốt lõi kỹ thuật ​

Phép toán lowbit ​

Nền tảng của toàn bộ Fenwick Tree nằm ở một dòng code duy nhất:

lowbit(i) = i & (-i)

Trong biểu diễn bù hai (two's complement), -i đảo tất cả bit rồi cộng 1. Kết quả i & (-i) chỉ giữ lại bit 1 thấp nhất của i. Đây là phép toán O(1) trên mọi CPU hiện đại.

Prefix Sum Query — O(log n) ​

Đi từ index i về 0, mỗi bước bỏ lowbit. Mỗi node trên đường đi lưu tổng một đoạn con — cộng tất cả lại được prefix sum.

cpp
int bit[MAXN]; // 1-indexed

int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += bit[i];
    return sum;
}

int rangeQuery(int L, int R) {
    return query(R) - query(L - 1);
}
python
bit = [0] * (n + 1)  # 1-indexed

def query(i: int) -> int:
    total = 0
    while i > 0:
        total += bit[i]
        i -= i & (-i)
    return total

def range_query(L: int, R: int) -> int:
    return query(R) - query(L - 1)
java
int[] bit; // 1-indexed

int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += bit[i];
    return sum;
}

int rangeQuery(int L, int R) {
    return query(R) - query(L - 1);
}
go
var bit []int // 1-indexed

func query(i int) int {
    sum := 0
    for ; i > 0; i -= i & (-i) {
        sum += bit[i]
    }
    return sum
}

func rangeQuery(L, R int) int {
    return query(R) - query(L-1)
}

Point Update — O(log n) ​

Đi từ index i lên n, mỗi bước cộng lowbit. Cập nhật tất cả node chứa index i trong phạm vi quản lý.

cpp
void update(int i, int delta) {
    for (; i <= n; i += i & (-i))
        bit[i] += delta;
}
python
def update(i: int, delta: int) -> None:
    while i <= n:
        bit[i] += delta
        i += i & (-i)
java
void update(int i, int delta) {
    for (; i <= n; i += i & (-i))
        bit[i] += delta;
}
go
func update(i, delta int) {
    for ; i <= n; i += i & (-i) {
        bit[i] += delta
    }
}

Build từ mảng — O(n) ​

Thay vì gọi update n lần (O(n log n)), ta build trực tiếp trong O(n): copy giá trị vào bit array, sau đó mỗi node cộng giá trị lên node cha trực tiếp.

cpp
void build(int a[], int n) {
    for (int i = 1; i <= n; i++) bit[i] = a[i];
    for (int i = 1; i <= n; i++) {
        int parent = i + (i & (-i));
        if (parent <= n) bit[parent] += bit[i];
    }
}
python
def build(a: list[int]) -> None:
    n = len(a)
    for i in range(1, n + 1):
        bit[i] = a[i]
    for i in range(1, n + 1):
        parent = i + (i & (-i))
        if parent <= n:
            bit[parent] += bit[i]
java
void build(int[] a, int n) {
    for (int i = 1; i <= n; i++) bit[i] = a[i];
    for (int i = 1; i <= n; i++) {
        int parent = i + (i & (-i));
        if (parent <= n) bit[parent] += bit[i];
    }
}
go
func build(a []int, n int) {
    for i := 1; i <= n; i++ {
        bit[i] = a[i]
    }
    for i := 1; i <= n; i++ {
        parent := i + (i & (-i))
        if parent <= n {
            bit[parent] += bit[i]
        }
    }
}

Fenwick Tree 2D ​

Mở rộng lên 2 chiều: mỗi thao tác lồng hai vòng lặp lowbit, cho phép tính tổng hình chữ nhật trong ma trận.

cpp
int bit2d[MAXN][MAXN];
int rows, cols;

void update2D(int x, int y, int delta) {
    for (int i = x; i <= rows; i += i & (-i))
        for (int j = y; j <= cols; j += j & (-j))
            bit2d[i][j] += delta;
}

int query2D(int x, int y) {
    int sum = 0;
    for (int i = x; i > 0; i -= i & (-i))
        for (int j = y; j > 0; j -= j & (-j))
            sum += bit2d[i][j];
    return sum;
}

// Tổng hình chữ nhật [(x1,y1), (x2,y2)]
int rectSum(int x1, int y1, int x2, int y2) {
    return query2D(x2, y2) - query2D(x1-1, y2)
         - query2D(x2, y1-1) + query2D(x1-1, y1-1);
}
python
def update_2d(x: int, y: int, delta: int) -> None:
    i = x
    while i <= rows:
        j = y
        while j <= cols:
            bit2d[i][j] += delta
            j += j & (-j)
        i += i & (-i)

def query_2d(x: int, y: int) -> int:
    total = 0
    i = x
    while i > 0:
        j = y
        while j > 0:
            total += bit2d[i][j]
            j -= j & (-j)
        i -= i & (-i)
    return total

def rect_sum(x1: int, y1: int, x2: int, y2: int) -> int:
    return (query_2d(x2, y2) - query_2d(x1-1, y2)
          - query_2d(x2, y1-1) + query_2d(x1-1, y1-1))
java
int[][] bit2d;
int rows, cols;

void update2D(int x, int y, int delta) {
    for (int i = x; i <= rows; i += i & (-i))
        for (int j = y; j <= cols; j += j & (-j))
            bit2d[i][j] += delta;
}

int query2D(int x, int y) {
    int sum = 0;
    for (int i = x; i > 0; i -= i & (-i))
        for (int j = y; j > 0; j -= j & (-j))
            sum += bit2d[i][j];
    return sum;
}

int rectSum(int x1, int y1, int x2, int y2) {
    return query2D(x2, y2) - query2D(x1-1, y2)
         - query2D(x2, y1-1) + query2D(x1-1, y1-1);
}
go
func update2D(bit2d [][]int, rows, cols, x, y, delta int) {
    for i := x; i <= rows; i += i & (-i) {
        for j := y; j <= cols; j += j & (-j) {
            bit2d[i][j] += delta
        }
    }
}

func query2D(bit2d [][]int, x, y int) int {
    sum := 0
    for i := x; i > 0; i -= i & (-i) {
        for j := y; j > 0; j -= j & (-j) {
            sum += bit2d[i][j]
        }
    }
    return sum
}

func rectSum(bit2d [][]int, x1, y1, x2, y2 int) int {
    return query2D(bit2d, x2, y2) - query2D(bit2d, x1-1, y2) -
           query2D(bit2d, x2, y1-1) + query2D(bit2d, x1-1, y1-1)
}

Độ phức tạp 2D BIT: O(log n × log m) cho mỗi thao tác, bộ nhớ O(n × m).

Thực chiến ​

Tình huống: Đếm nghịch thế (Inversion Count) ​

Bối cảnh: Hệ thống ranking cần đo mức độ "hỗn loạn" của một dãy xếp hạng so với thứ tự chuẩn. Nghịch thế là cặp (i, j) với i < j nhưng a[i] > a[j]. Brute force O(n²) không chấp nhận được với n = 10⁶.

Mục tiêu: Đếm số nghịch thế trong O(n log n).

cpp
#include <vector>
#include <algorithm>

long long countInversions(std::vector<int>& arr) {
    int n = arr.size();
    // Nén tọa độ
    std::vector<int> sorted = arr;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();

    std::vector<int> bit(m + 1, 0);
    auto update = [&](int i) {
        for (; i <= m; i += i & (-i)) bit[i]++;
    };
    auto query = [&](int i) -> int {
        int s = 0;
        for (; i > 0; i -= i & (-i)) s += bit[i];
        return s;
    };

    long long inversions = 0;
    for (int i = n - 1; i >= 0; i--) {
        int rank = std::lower_bound(sorted.begin(), sorted.end(), arr[i])
                 - sorted.begin() + 1;
        inversions += query(rank - 1);
        update(rank);
    }
    return inversions;
}
python
from bisect import bisect_left

def count_inversions(arr: list[int]) -> int:
    # Nén tọa độ
    sorted_unique = sorted(set(arr))
    rank_map = {v: i + 1 for i, v in enumerate(sorted_unique)}
    m = len(sorted_unique)

    bit = [0] * (m + 1)

    def update(i: int) -> None:
        while i <= m:
            bit[i] += 1
            i += i & (-i)

    def query(i: int) -> int:
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    inversions = 0
    for val in reversed(arr):
        rank = rank_map[val]
        inversions += query(rank - 1)
        update(rank)
    return inversions
java
import java.util.*;

public class InversionCounter {
    public static long countInversions(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> rank = new HashMap<>();
        int r = 0;
        for (int v : sorted)
            if (!rank.containsKey(v)) rank.put(v, ++r);
        int m = r;

        int[] bit = new int[m + 1];
        long inversions = 0;
        for (int i = n - 1; i >= 0; i--) {
            int rk = rank.get(arr[i]);
            for (int j = rk - 1; j > 0; j -= j & (-j)) inversions += bit[j];
            for (int j = rk; j <= m; j += j & (-j)) bit[j]++;
        }
        return inversions;
    }
}
go
import "sort"

func countInversions(arr []int) int64 {
    n := len(arr)
    sorted := make([]int, n)
    copy(sorted, arr)
    sort.Ints(sorted)
    // Nén tọa độ
    unique := []int{sorted[0]}
    for i := 1; i < n; i++ {
        if sorted[i] != sorted[i-1] {
            unique = append(unique, sorted[i])
        }
    }
    rankMap := map[int]int{}
    for i, v := range unique {
        rankMap[v] = i + 1
    }
    m := len(unique)
    bit := make([]int, m+1)

    query := func(i int) int {
        s := 0
        for ; i > 0; i -= i & (-i) { s += bit[i] }
        return s
    }
    update := func(i int) {
        for ; i <= m; i += i & (-i) { bit[i]++ }
    }

    var inversions int64
    for i := n - 1; i >= 0; i-- {
        rk := rankMap[arr[i]]
        inversions += int64(query(rk - 1))
        update(rk)
    }
    return inversions
}

Phân tích:

  • Nén tọa độ O(n log n) để đưa giá trị về range [1..m].
  • Duyệt từ phải sang trái, mỗi phần tử: query O(log m) + update O(log m).
  • Tổng: O(n log n). Space O(n) — tốt hơn merge sort approach vì không cần mảng phụ lớn.

Sai lầm điển hình ​

❌ Sai lầm 1: Dùng Fenwick Tree cho min/max query ​

Vấn đề: Cố gắng dùng Fenwick Tree để trả lời range min/max.

Tại sao sai: Fenwick Tree dựa trên phép trừ để tính range query: range(L, R) = prefix(R) - prefix(L-1). Phép min/max không có nghịch đảo — không thể "trừ" min đi. Chỉ các phép toán có nghịch đảo (cộng-trừ, xor) mới hoạt động.

python
# ĐÚNG: dùng Segment Tree cho min/max
# Fenwick Tree chỉ phù hợp cho: sum, xor, count

❌ Sai lầm 2: Dùng 0-indexed cho Fenwick Tree ​

Vấn đề: Khởi tạo bit array từ index 0.

python
# SAI: index 0 gây lặp vô hạn
bit = [0] * n
def update(i, delta):
    while i < n:
        bit[i] += delta
        i += i & (-i)  # 0 & (-0) = 0 → lặp vô hạn!

Tại sao sai: 0 & (-0) = 0, nên i += 0 lặp mãi. Tương tự, query từ 0 cũng lặp vô hạn. Fenwick Tree BẮT BUỘC 1-indexed.

python
# ĐÚNG: luôn 1-indexed, cộng 1 khi convert từ 0-indexed
bit = [0] * (n + 1)
def update(i, delta):
    i += 1  # convert 0-indexed sang 1-indexed
    while i <= n:
        bit[i] += delta
        i += i & (-i)

❌ Sai lầm 3: Quên nén tọa độ khi giá trị lớn ​

Vấn đề: Mảng bit cần kích thước bằng giá trị lớn nhất. Nếu giá trị lên tới 10⁹, cấp phát mảng 10⁹ phần tử → MLE.

Tại sao sai: Fenwick Tree index theo giá trị, không theo vị trí. Với giá trị lớn, bắt buộc nén tọa độ (coordinate compression) để đưa về range [1..n].

❌ Sai lầm 4: Set value thay vì add delta ​

Vấn đề: Gọi update(i, new_value) khi hàm update thực chất cộng thêm delta.

Tại sao sai: Fenwick Tree update bằng delta (hiệu). Muốn set giá trị mới, phải tính delta = new_value - old_value rồi mới gọi update. Quên điều này dẫn đến giá trị tích lũy sai.

Under the Hood ​

Hiệu năng ​

Thao tácFenwick TreeSegment TreeGhi chú
BuildO(n)O(n)Fenwick build đơn giản hơn
QueryO(log n)O(log n)Fenwick có hằng số nhỏ hơn ~2-3x
UpdateO(log n)O(log n)Tương tự
Bộ nhớn + 14nFenwick tiết kiệm 4x
Code~15 dòng~50 dòngÍt bug hơn, dễ debug hơn

Nội bộ triển khai ​

Tại sao lowbit hoạt động? Trong biểu diễn bù hai: -i = ~i + 1. Khi AND với i, tất cả bit trên lowbit bị triệt tiêu (vì ~i đảo chúng), chỉ còn bit thấp nhất sống sót. Phép toán này chạy trong 1 chu kỳ CPU — không có overhead.

Cấu trúc ẩn của cây: Fenwick Tree không xây cây tường minh, nhưng quan hệ cha-con được encode trong biểu diễn nhị phân. Node i là con của node i + lowbit(i). Khi update index i, ta đi theo chuỗi cha: i → i + lowbit(i) → ... cho đến khi vượt n. Khi query prefix(i), ta đi theo chuỗi: i → i - lowbit(i) → ... cho đến 0.

So sánh cache performance: Fenwick Tree truy cập các phần tử cách nhau theo lũy thừa 2 — không hoàn toàn sequential nhưng vẫn tốt hơn Segment Tree (nhảy giữa các vùng cây). Trên thực tế, Fenwick nhanh hơn Segment Tree 2-3 lần cho cùng bài toán prefix sum.

Trade-offs ​

Tiêu chíFenwick Tree ✅Fenwick Tree ❌
Sum, XOR, countTối ưu—
Min, Max, GCD—Không hỗ trợ → dùng Segment Tree
Range update—Phức tạp → dùng Segment Tree + lazy
Bộ nhớ1/4 so với Segment Tree—
Dễ code15 dòng, ít bug—
Mở rộng 2DDễ dàng—

Quy tắc vàng: Nếu bài toán chỉ cần prefix sum + point update (hoặc XOR, count), Fenwick Tree luôn là lựa chọn đầu tiên. Mọi yêu cầu phức tạp hơn → chuyển sang Segment Tree.

Checklist ghi nhớ ​

✅ Checklist triển khai

Cơ bản

  • [ ] Luôn dùng 1-indexed — index 0 gây lặp vô hạn
  • [ ] lowbit(i) = i & (-i) — học thuộc, không cần suy nghĩ
  • [ ] Query: bỏ lowbit (i -= i & (-i)), Update: cộng lowbit (i += i & (-i))

Thiết kế

  • [ ] Chỉ dùng cho phép toán có nghịch đảo (sum, xor, count)
  • [ ] Min/Max/GCD → chuyển sang Segment Tree
  • [ ] Giá trị lớn → nén tọa độ trước khi dùng

Production

  • [ ] Build O(n) thay vì n lần update O(n log n)
  • [ ] Update bằng delta, không phải giá trị mới — tính delta = new - old
  • [ ] Kiểm tra overflow khi tổng vượt int32

Bài tập luyện tập ​

Bài 1: Prefix Sum Query — Foundation ​

Đề bài: Cho mảng n phần tử, xử lý q query:

  • 1 i delta: cộng delta vào a[i]
  • 2 L R: in tổng a[L..R]

Ràng buộc: 1 ≤ n, q ≤ 10⁵.

🧠 Quiz

Câu hỏi: Fenwick Tree và Segment Tree cùng hỗ trợ range sum query O(log n). Khi nào nên chọn Fenwick Tree?

  • [ ] A. Khi cần range update với lazy propagation
  • [x] B. Khi chỉ cần point update + prefix/range sum
  • [ ] C. Khi cần range min/max query
  • [ ] D. Khi dữ liệu là số thực dấu phẩy động Giải thích: Fenwick Tree tối ưu cho prefix sum + point update vì code ngắn, bộ nhớ nhỏ, hằng số thời gian thấp. Lazy propagation (A) và min/max (C) cần Segment Tree.
💡 Gợi ý
  • Dùng Fenwick Tree 1-indexed.
  • Range sum [L, R] = prefix(R) - prefix(L - 1).
✅ Lời giải
python
import sys
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    bit = [0] * (n + 1)
    # Build O(n)
    for i in range(1, n + 1):
        bit[i] = a[i - 1]
    for i in range(1, n + 1):
        p = i + (i & (-i))
        if p <= n:
            bit[p] += bit[i]

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

    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    out = []
    for _ in range(q):
        t, x, y = map(int, input().split())
        if t == 1:
            update(x, y)
        else:
            out.append(str(query(y) - query(x - 1)))
    print('\n'.join(out))

Phân tích: Time O((n + q) log n), Space O(n). Build O(n), mỗi query/update O(log n).

Bài 2: Đếm nghịch thế — Advanced ​

Đề bài: Cho mảng n phần tử, đếm số cặp (i, j) với i < j mà a[i] > a[j].

Ràng buộc: 1 ≤ n ≤ 5 × 10⁵, 1 ≤ a[i] ≤ 10⁹.

💡 Gợi ý
  • Nén tọa độ: sort unique values, map mỗi giá trị thành rank 1..m.
  • Duyệt từ phải sang trái, dùng Fenwick Tree đếm phần tử nhỏ hơn đã gặp.
✅ Lời giải

Xem code trong phần Thực chiến ở trên. Giải thuật: duyệt ngược, mỗi phần tử query số phần tử nhỏ hơn nó ở bên phải (đã insert vào BIT), rồi insert rank của nó.

Phân tích: Time O(n log n), Space O(n).

Liên kết học tiếp ​

📚 Bài liên quan

Bài liên quan trong Penalgo

Từ khóa glossary: Fenwick Tree, Binary Indexed Tree, BIT, prefix sum, lowbit, point update, coordinate compression

Tìm kiếm liên quan: cây chỉ số nhị phân, truy vấn tiền tố, đếm nghịch thế, nén tọa độ

Professional Engineering Standards | © 2025 HPN Corporation