Cấu trúc dữ liệu và Giải thuật Bài 60: Cây chỉ mục nhị phân (Fenwick Tree / BIT) - Tối ưu hóa truy vấn khoảng và cập nhật điểm với không gian tối thiểu.

Ở Bài 58, chúng ta đã chinh phục Cây Phân Đoạn (Segment Tree) để giải quyết các bài toán truy vấn khoảng. Tuy nhiên, Segment Tree có một điểm trừ nhỏ về mặt tài nguyên: Nó đòi hỏi dung lượng bộ nhớ cấp phát lớn gấp 4 lần mảng gốc ($4n$) và cấu trúc code tương đối cồng kềnh với nhiều hàm đệ quy phân nhánh.

Nếu bài toán của bạn chỉ cần thực hiện hai thao tác: Cập nhật một điểm (Point Update) và Truy vấn tổng tiền tố/khoảng (Prefix/Range Sum Query) mà không cần các tính năng phức tạp của Lazy Propagation, có một kiệt tác cấu trúc dữ liệu khác ra đời năm 1994 bởi Peter Fenwick, giải quyết trọn vẹn mọi yêu cầu với không gian tối thiểu bằng đúng mảng gốc ($O(n)$) và mã nguồn cực kỳ ngắn gọn: Cây chỉ mục nhị phân (Fenwick Tree / Binary Indexed Tree - BIT).

1. Phép Thuật Từ Bitwise: i & -i

Bí mật sống còn của Fenwick Tree không nằm ở cấu trúc cây phức tạp, mà nằm ở một phép toán bitwise cực kỳ tinh vi: i & -i.

• Trong hệ thống máy tính, số âm được biểu diễn bằng mã bù 2 (Two's complement). Khi bạn thực hiện phép tính i & -i trên một số nguyên dương i, kết quả trả về sẽ cô lập chính xác bit 1 thấp nhất (Lowest Set Bit) của số đó.
• Ví dụ: i = 6 (Hệ nhị phân: 0110). Bit 1 thấp nhất nằm ở vị trí thứ 2 (giá trị 2). Phép toán 6 & -6 sẽ trả về 2.
• Ví dụ: i = 12 (Hệ nhị phân: 1100). Bit 1 thấp nhất có giá trị 4. Phép toán 12 & -12 sẽ trả về 4.

Fenwick Tree sử dụng nguyên lý này để ép các tổng tiền tố phân rã thành một chuỗi các khoảng có độ dài bằng chính các lũy thừa của 2. Thay vì tạo ra một cây nhị phân thực thụ bằng các con trỏ Left và Right, Fenwick Tree lưu trữ toàn bộ cấu trúc cây bên trong một Mảng 1 chiều (Slice) duy nhất có kích thước $N + 1$.

2. Hai Thao Tác Cốt Lõi: Update và Query

A. Truy vấn Tiền tố (Prefix Sum Query)

Để tính tổng từ phần tử đầu tiên đến vị trí idx:

1. Bắt đầu từ chỉ mục idx.
2. Cộng dồn giá trị tại ô nhớ hiện tại của mảng BIT.
3. Nhảy lùi về phía trước bằng cách trừ đi bit thấp nhất: idx -= idx & -idx.
4. Lặp lại cho đến khi idx chạy về 0.

Quá trình này chỉ nhảy qua tối đa số lượng bit của idx, đảm bảo tốc độ siêu tốc $O(\log n)$. Để tính tổng trong một khoảng bất kỳ từ l đến r, bạn chỉ cần tính Query(r) - Query(l - 1).

B. Cập nhật Điểm (Point Update)

Khi giá trị tại một vị trí idx thay đổi một lượng delta:

1. Bắt đầu từ chỉ mục idx.
2. Cộng delta vào ô nhớ hiện tại trên mảng BIT.
3. Nhảy tiến về phía trước bằng cách cộng thêm bit thấp nhất: idx += idx & -idx.
4. Lặp lại cho đến khi vượt quá kích thước $N$ của mảng.

Thao tác này cũng diễn ra trong thời gian $O(\log n)$ vì số lần "nhảy cóc" đúng bằng số lượng bit của chỉ mục.

3. Triển Khai Fenwick Tree Tinh Gọn Bằng Golang

Đoạn code dưới đây cài đặt một Fenwick Tree hoàn chỉnh, sạch sẽ và tối ưu hóa hiệu năng cho các ứng dụng backend:

package main

import "fmt"

type FenwickTree struct {
    tree []int
    n    int
}

// Khởi tạo Fenwick Tree với kích thước n
func NewFenwickTree(n int) *FenwickTree {
    return &FenwickTree{
        tree: make([]int, n+1), // BIT thường sử dụng index bắt đầu từ 1
        n:    n,
    }
}

// 1. Cập nhật điểm (Point Update): Cộng thêm delta vào vị trí idx (1-indexed)
// Độ phức tạp thời gian: O(log n)
func (ft *FenwickTree) Update(idx int, delta int) {
    for idx <= ft.n {
        ft.tree[idx] += delta
        idx += idx & -idx // Nhảy tiến lên theo bit thấp nhất
    }
}

// 2. Truy vấn tổng tiền tố từ 1 đến idx (Prefix Sum Query)
// Độ phức tạp thời gian: O(log n)
func (ft *FenwickTree) Query(idx int) int {
    sum := 0
    for idx > 0 {
        sum += ft.tree[idx]
        idx -= idx & -idx // Nhảy lùi lại theo bit thấp nhất
    }
    return sum
}

// 3. Truy vấn tổng khoảng [l, r] (Range Sum Query)
func (ft *FenwickTree) RangeQuery(l, r int) int {
    return ft.Query(r) - ft.Query(l-1)
}

4. So Sánh Segment Tree Và Fenwick Tree

Nếu bài toán chỉ yêu cầu Point Update và Range/Prefix Query, Fenwick Tree luôn là lựa chọn ưu tiên hàng đầu nhờ mã nguồn tối giản và hệ số hằng số (constant factor) trong thực thi cực kỳ nhỏ.

5. Ứng Dụng Thực Tế Trong Hệ Thống Lớn

• Đếm số cặp nghịch thế (Inversion Counting): Được sử dụng trong các hệ thống phân tích dữ liệu thống kê để đo lường mức độ "lệch pha" hoặc độ tương đồng giữa các tập hợp thứ hạng (ví dụ: thuật toán sắp xếp, hệ thống gợi ý sản phẩm dựa trên sở thích người dùng).
• Quản lý tần suất thời gian thực (Real-time Frequency Tables): Các hệ thống đếm sự kiện thời gian thực (như số lượng click, lượt xem sản phẩm theo danh mục động) sử dụng BIT để vừa cập nhật liên tục vừa truy vấn tổng nhanh chóng mà không làm phát sinh chi phí RAM lớn.

💡 Lời Kết

Chương 12 đã mở rộng tầm nhìn của chúng ta qua các cấu trúc truy vấn khoảng nâng cao. Khi các bài toán hệ thống chuyển dịch sang mạng lưới phức tạp đòi hỏi điều phối tài nguyên tối đa, chúng ta sẽ bước sang một trong những chương gai góc và đẹp đẽ nhất của khoa học máy tính: Đồ thị nâng cao và Luồng mạng (Advanced Graph & Network Flow).