Cấu trúc dữ liệu và Giải thuật Bài 102: Cây chỉ số nhị phân (Fenwick Tree / BIT) - Tối ưu hóa không gian cho bài toán truy vấn tổng.

Sau khi làm chủ Cây phân đoạn (Segment Tree) ở Bài 101 với sự linh hoạt tuyệt đối, hôm nay chúng ta tiếp tục khám phá một cấu trúc dữ liệu thanh thoát và tối ưu hơn hẳn về mặt không gian cũng như hằng số thời gian thực thi: Cây chỉ số nhị phân (Fenwick Tree hay Binary Indexed Tree - BIT).

Trong các bài toán hệ thống yêu cầu thống kê tần suất, đếm số lượng phần tử nhỏ hơn trong một khoảng (ví dụ: các bài toán đếm số lượng giao dịch trong khoảng giá trị tại các hệ thống tài chính), Segment Tree đôi khi tỏ ra quá cồng kềnh với lượng bộ nhớ phụ trợ lên đến $4N$ . Vào năm 1994, Peter Fenwick đã giới thiệu BIT để giải quyết trọn vẹn bài toán Truy vấn tổng tiền tố (Prefix Sum) và Cập nhật điểm (Point Update) chỉ với $O(N)$ không gian và code cài đặt cực kỳ ngắn gọn.

1. Trực giác đằng sau Fenwick Tree

Bí mật của Fenwick Tree nằm ở cách biểu diễn số nguyên dưới dạng hệ nhị phân (Binary representation).

Mọi số nguyên dương đều có thể phân rã thành tổng các lũy thừa của 2. Ví dụ, số $13$ trong hệ nhị phân là 1101 (tương ứng với $8 + 4 + 1$ ). Thay vì lưu trữ toàn bộ cây nhị phân đầy đủ như Segment Tree, một mảng BIT kích thước $N$ sẽ tận dụng chính các vị trí bit 1 trong chỉ số của nó để quản lý các khoảng có độ dài bằng chính lũy thừa của 2 tương ứng.

Phép toán cốt lõi làm nên toàn bộ sự kỳ diệu của BIT chính là:

$\text{LSB}(i) = i \ \& \ (-i)$

Phép toán này giúp trích xuất ra bit 1 thấp nhất (Lowest Set Bit) của một số nguyên $i$ . Ví dụ, nếu $i = 6$ (nhị phân 0110), thì $\text{LSB}(6) = 2$ (nhị phân 0010). Nút tại vị trí $6$ trong BIT sẽ chịu trách nhiệm quản lý đúng $2$ phần tử liên tiếp kết thúc tại $6$ (tức là khoảng $[5, 6]$ ).

2. Hai thao tác cơ bản trên BIT

Nhờ có $\text{LSB}(i)$ , hai thao tác quan trọng nhất của BIT được thực hiện chỉ bằng các vòng lặp dịch bit đơn giản:

A. Truy vấn tổng tiền tố (Prefix Sum Query)

Để tính tổng từ đầu mảng đến vị trí $i$ :

Lấy giá trị tại tree[i].
Nhảy về nút cha bằng cách trừ đi $\text{LSB}(i)$ : i -= i & (-i).
Lặp lại cho đến khi $i = 0$ .

Độ phức tạp thời gian: $O(\log N)$ vì số lượng bit 1 trong một số nguyên tối đa bằng số bit của nó.

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

Khi giá trị tại một phần tử $i$ thay đổi một lượng $\Delta$ :

Cộng $\Delta$ vào tree[i].
Nhảy tới các nút chịu ảnh hưởng ở cấp cao hơn bằng cách cộng thêm $\text{LSB}(i)$ : i += i & (-i).
Lặp lại cho đến khi vượt quá kích thước $N$ của mảng.

Độ phức tạp thời gian: $O(\log N)$ .

4. Hiện thực hóa Fenwick Tree bằng Golang

Đoạn code Golang dưới đây cài đặt một Fenwick Tree hỗ trợ truy vấn tổng khoảng từ $L$ đến $R$ và cập nhật điểm một cách cực kỳ tối ưu:

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,
	}
}

// Cộng thêm delta vào phần tử tại vị trí idx (1-based index)
func (ft *FenwickTree) Add(idx int, delta int) {
	for idx <= ft.n {
		ft.tree[idx] += delta
		idx += idx & -idx // Nhảy lên các nút cha quản lý vùng lớn hơn
	}
}

// Tính tổng các phần tử từ 1 đến idx (Prefix Sum)
func (ft *FenwickTree) Query(idx int) int {
	sum := 0
	for idx > 0 {
		sum += ft.tree[idx]
		idx -= idx & -idx // Nhảy lùi về các nút trước đó
	}
	return sum
}

// Tính tổng khoảng từ l đến r (Range Sum Query từ l tới r)
func (ft *FenwickTree) RangeQuery(l, r int) int {
	return ft.Query(r) - ft.Query(l-1)
}

func main() {
	// Mảng ban đầu (giả sử có 6 phần tử: 1, 3, 5, 7, 9, 11)
	// Ta khởi tạo BIT bằng cách lần lượt Add từng phần tử vào vị trí tương ứng
	data := []int{0, 1, 3, 5, 7, 9, 11} // Dùng index từ 1, phần tử index 0 bỏ qua
	n := len(data) - 1

	ft := NewFenwickTree(n)
	for i := 1; i <= n; i++ {
		ft.Add(i, data[i])
	}

	// 1. Truy vấn tổng khoảng từ index 2 đến 5 (các số: 3, 5, 7, 9)
	sum := ft.RangeQuery(2, 5)
	fmt.Printf("Tổng khoảng [2, 5] ban đầu: %d\n", sum) // Kết quả: 3+5+7+9 = 24

	// 2. Cập nhật: Cộng thêm 15 vào phần tử tại index 3 (đang là 5, nay thành 5 + 15 = 20)
	// Để tăng từ 5 lên 20, ta truyền delta = 20 - 5 = 15 vào hàm Add
	fmt.Println("Cập nhật phần tử index 3 tăng thêm 15...")
	ft.Add(3, 15)

	// 3. Truy vấn lại khoảng từ 2 đến 5 sau khi cập nhật
	sumAfterUpdate := ft.RangeQuery(2, 5)
	fmt.Printf("Tổng khoảng [2, 5] sau khi cập nhật: %d\n", sumAfterUpdate) // Kết quả: 3+20+7+9 = 39
}

5. So sánh Segment Tree và Fenwick Tree

Bộ nhớ (Space): Fenwick Tree chỉ tốn đúng $O(N)$ không gian bộ nhớ phụ trợ, trong khi Segment Tree tốn $O(4N)$ .
Tốc độ thực thi (Constant Factor): Do không có đệ quy phức tạp và chỉ dùng các phép toán bitwise trực tiếp trên mảng 1 chiều, Fenwick Tree chạy nhanh hơn đáng kể so với Segment Tree trong các bài toán thuần tính tổng hoặc đếm tần suất.
Tính linh hoạt: Segment Tree vượt trội hơn khi bài toán yêu cầu tìm kiếm giá trị lớn nhất/nhỏ nhất (Range Min/Max Query) hoặc cập nhật toàn bộ một khoảng (Lazy Propagation), những điều mà một Fenwick Tree tiêu chuẩn khó hoặc không thể làm trực

cấu trúc dữ liệu