Bài 31.1. Khái niệm và cài đặt cơ bản Fenwick Tree

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật!

Trong bài viết lần này, chúng ta sẽ cùng khám phá một cấu trúc dữ liệu mạnh mẽ và hiệu quả cho các bài toán liên quan đến tổng tiền tố (prefix sum) và cập nhật tại một điểm (point update): Fenwick Tree, hay còn gọi là Binary Indexed Tree (BIT).

Nếu bạn thường xuyên gặp các bài toán yêu cầu vừa tính tổng một đoạn con trong mảng, vừa thay đổi giá trị của các phần tử trong mảng đó, Fenwick Tree chính là một trong những công cụ tối ưu mà bạn cần biết.

Bài Toán Đặt Ra

Hãy tưởng tượng bạn có một mảng A gồm N phần tử. Bạn cần thực hiện hai loại thao tác một cách nhanh chóng:

Cập nhật điểm (Point Update): Thay đổi giá trị của một phần tử tại chỉ mục i nào đó.
Truy vấn tổng tiền tố (Prefix Sum Query): Tính tổng các phần tử từ chỉ mục đầu tiên đến chỉ mục j (tức là A[1] + A[2] + ... + A[j]).

Từ truy vấn tổng tiền tố, chúng ta có thể dễ dàng tính được tổng một đoạn con từ chỉ mục l đến r (Sum(l, r)) bằng công thức: Sum(l, r) = PrefixSum(r) - PrefixSum(l-1).

Nếu chỉ có truy vấn tổng tiền tố và không có cập nhật, chúng ta có thể dùng mảng tổng tiền tố (prefix sum array) truyền thống, cho truy vấn O(1) nhưng cập nhật một điểm sẽ tốn O(N). Ngược lại, nếu chỉ có cập nhật và truy vấn tại điểm, mảng ban đầu là đủ, cập nhật O(1) nhưng tính tổng tiền tố tốn O(N).

Fenwick Tree mang đến sự cân bằng: cả thao tác cập nhật điểm và truy vấn tổng tiền tố đều có độ phức tạp thời gian là O(log N), nơi N là kích thước mảng.

Khái Niệm Cơ Bản của Fenwick Tree (BIT)

Fenwick Tree không phải là một cấu trúc cây theo nghĩa đen với các node và con trỏ như Binary Search Tree. Nó thường được cài đặt bằng một mảng đơn giản, gọi là mảng BIT hoặc Fenwick Tree.

Bí mật đằng sau Fenwick Tree nằm ở cách mỗi phần tử BIT[i] lưu trữ tổng của một khoảng xác định các phần tử trong mảng gốc, dựa trên biểu diễn nhị phân của chỉ mục i.

Cụ thể, phần tử BIT[i] lưu trữ tổng của các phần tử trong mảng gốc từ chỉ mục i - (i & -i) + 1 đến chỉ mục i.

Biểu thức i & -i trong toán học máy tính tính ra giá trị của bit thấp nhất đang bật (lowest set bit) của i. Ví dụ:

i = 1 (0001 nhị phân), i & -i = 1 (0001) -> BIT[1] lưu tổng từ 1-1+1=1 đến 1: A[1]
i = 2 (0010 nhị phân), i & -i = 2 (0010) -> BIT[2] lưu tổng từ 2-2+1=1 đến 2: A[1] + A[2]
i = 3 (0011 nhị phân), i & -i = 1 (0001) -> BIT[3] lưu tổng từ 3-1+1=3 đến 3: A[3]
i = 4 (0100 nhị phân), i & -i = 4 (0100) -> BIT[4] lưu tổng từ 4-4+1=1 đến 4: A[1] + A[2] + A[3] + A[4]
i = 5 (0101 nhị phân), i & -i = 1 (0001) -> BIT[5] lưu tổng từ 5-1+1=5 đến 5: A[5]
i = 6 (0110 nhị phân), i & -i = 2 (0010) -> BIT[6] lưu tổng từ 6-2+1=5 đến 6: A[5] + A[6]
i = 7 (0111 nhị phân), i & -i = 1 (0001) -> BIT[7] lưu tổng từ 7-1+1=7 đến 7: A[7]
i = 8 (1000 nhị phân), i & -i = 8 (1000) -> BIT[8] lưu tổng từ 8-8+1=1 đến 8: A[1] + ... + A[8]

Nhận thấy rằng kích thước của đoạn mà BIT[i] quản lý luôn là một lũy thừa của 2, bằng chính giá trị i & -i.

Để đơn giản trong cài đặt, Fenwick Tree thường sử dụng chỉ mục 1-based (phần tử đầu tiên là index 1 thay vì 0). Mảng BIT sẽ có kích thước lớn hơn mảng gốc 1 đơn vị.

Cài Đặt Fenwick Tree Cơ Bản (C++)

Chúng ta sẽ cài đặt hai thao tác chính: update và query. Kích thước của mảng Fenwick Tree sẽ là N + 1 nếu mảng gốc có N phần tử và chúng ta dùng 1-based indexing cho các thao tác BIT.

Hàm `update(index, value)`

Hàm này dùng để thêm một giá trị value vào phần tử tại index trong mảng gốc (conceptually) và cập nhật các node tương ứng trong cây Fenwick Tree.

Khi một giá trị tại index thay đổi, chúng ta cần cập nhật tất cả các node BIT[j] mà khoảng tổng của chúng bao gồm index. Để làm điều này, chúng ta bắt đầu từ index và di chuyển lên các node "cha". Node cha tiếp theo của index là index + (index & -index). Chúng ta lặp lại quá trình này cho đến khi vượt quá kích thước mảng.

void update(int index, int value, vector<long long>& bit, int size) {
    // index là chỉ mục 1-based
    // value là giá trị muốn THÊM vào phần tử tại index
    while (index <= size) {
        bit[index] += value;
        index += index & (-index); // Bước nhảy tới node cha tiếp theo
    }
}

Giải thích code:
- Hàm nhận vào index (chỉ mục cần cập nhật, 1-based), value (giá trị delta muốn thêm/bớt), mảng bit (Fenwick Tree), và size (kích thước mảng gốc).
- Vòng lặp while (index <= size) đảm bảo chúng ta chỉ cập nhật các node trong phạm vi hợp lệ của Fenwick Tree.
- bit[index] += value; thực hiện việc thêm giá trị value vào node hiện tại.
- index += index & (-index); là bước nhảy quan trọng. Nó di chuyển index đến node cha gần nhất có phạm vi tổng bao gồm phạm vi hiện tại. Điều này dựa trên tính chất của biểu diễn nhị phân và cách cây BIT được "xây dựng ngầm".

Hàm `query(index)`

Hàm này dùng để tính tổng tiền tố của các phần tử từ chỉ mục 1 đến index trong mảng gốc.

Để tính tổng đến index, chúng ta cần cộng dồn giá trị của các node BIT[j] mà phạm vi tổng của chúng kết thúc tại hoặc trước index và cùng nhau bao phủ toàn bộ tiền tố từ 1 đến index. Để làm điều này, chúng ta bắt đầu từ index và di chuyển xuống các node "tổ tiên". Node tổ tiên tiếp theo của index là index - (index & -index). Chúng ta lặp lại quá trình này cho đến khi index trở thành 0.

long long query(int index, const vector<long long>& bit) {
    // index là chỉ mục 1-based
    long long sum = 0;
    while (index > 0) {
        sum += bit[index];
        index -= index & (-index); // Bước nhảy lùi về node tổ tiên
    }
    return sum;
}

Giải thích code:
- Hàm nhận vào index (chỉ mục cuối của tiền tố, 1-based) và mảng bit.
- Biến sum được khởi tạo để lưu trữ tổng.
- Vòng lặp while (index > 0) tiếp tục cho đến khi chúng ta đi hết các node cần thiết để bao phủ tiền tố từ 1 đến index.
- sum += bit[index]; cộng giá trị của node hiện tại vào tổng.
- index -= index & (-index); là bước nhảy lùi quan trọng. Nó di chuyển index đến node tổ tiên (hoặc node trước đó trong cấu trúc BIT) có phạm vi tổng kết thúc tại hoặc trước phạm vi hiện tại, giúp bao phủ các phần còn lại của tiền tố.

Hàm `range_sum(l, r)`

Như đã nói ở trên, tổng đoạn từ l đến r chỉ đơn giản là hiệu của hai tổng tiền tố.

long long range_sum(int l, int r, const vector<long long>& bit) {
    // l và r là chỉ mục 1-based, bao gồm cả l và r
    if (l > r) return 0; // Xử lý trường hợp đoạn không hợp lệ
    return query(r, bit) - query(l - 1, bit);
}

Giải thích code: Chỉ cần gọi hàm query hai lần và lấy hiệu. Chú ý là query(l - 1) tính tổng đến ngay trước chỉ mục l.

Xây dựng Fenwick Tree ban đầu (`build`)

Nếu bạn đã có sẵn mảng gốc và muốn xây dựng Fenwick Tree từ đầu, cách đơn giản nhất là khởi tạo mảng BIT toàn số 0, sau đó dùng hàm update để thêm giá trị của từng phần tử mảng gốc vào BIT.

// Hàm build Fenwick Tree từ mảng gốc (1-based)
void build(const vector<int>& arr, vector<long long>& bit, int size) {
    // arr được giả định là mảng gốc 1-based, có size phần tử hữu ích
    // mảng bit cần có size + 1 phần tử
    // Khởi tạo bit toàn 0 là bước đầu tiên (thường làm khi khai báo)
    // vector<long long> bit(size + 1, 0);

    for (int i = 1; i <= size; ++i) {
        update(i, arr[i], bit, size); // Thêm giá trị của arr[i] vào BIT
    }
}

Giải thích code: Lặp qua từng phần tử của mảng gốc (từ index 1 đến size) và gọi update với giá trị của phần tử đó. Lưu ý rằng update(i, arr[i], ...) ở đây có nghĩa là thêm giá trị arr[i] vào vị trí i của BIT.

Ví Dụ Minh Hoạ Toàn Diện (C++)

Hãy cùng ghép các phần trên lại và xem Fenwick Tree hoạt động như thế nào với một ví dụ cụ thể.

#include <iostream>
#include <vector>
#include <numeric> // Cho các hàm tiện ích (không bắt buộc cho BIT core)

// --- Các hàm cài đặt Fenwick Tree (Sử dụng 1-based indexing cho các tham số index) ---

void update(int index, int value, vector<long long>& bit, int size) {
    // index là chỉ mục 1-based
    // value là giá trị muốn THÊM vào phần tử tại index
    while (index <= size) {
        bit[index] += value;
        index += index & (-index); // Bước nhảy tới node cha tiếp theo
    }
}

long long query(int index, const vector<long long>& bit) {
    // index là chỉ mục 1-based
    long long sum = 0;
    while (index > 0) {
        sum += bit[index];
        index -= index & (-index); // Bước nhảy lùi về node tổ tiên
    }
    return sum;
}

long long range_sum(int l, int r, const vector<long long>& bit) {
    // l và r là chỉ mục 1-based, bao gồm cả l và r
    if (l > r) return 0; // Xử lý trường hợp đoạn không hợp lệ
    return query(r, bit) - query(l - 1, bit);
}

// Hàm build Fenwick Tree từ mảng gốc (giả định mảng gốc là 1-based)
void build(const vector<int>& arr, vector<long long>& bit, int size) {
    // arr được giả định là mảng gốc 1-based, có size phần tử hữu ích từ index 1 đến size
    for (int i = 1; i <= size; ++i) {
        update(i, arr[i], bit, size); // Thêm giá trị của arr[i] vào BIT
    }
}

// --- Chương trình chính minh hoạ ---

int main() {
    // Giả sử mảng gốc của chúng ta (theo logic bài toán) có 10 phần tử,
    // tương ứng với các chỉ mục từ 1 đến 10.
    int n = 10;
    // Mảng ban đầu (ví dụ, giả định là 1-based cho dễ hình dung với BIT 1-based)
    // arr[0] sẽ không dùng, arr[1] = 1, arr[2] = 2, ... arr[10] = 10
    vector<int> initial_array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Mảng Fenwick Tree cần kích thước n + 1 cho 1-based indexing
    vector<long long> fenwick_tree(n + 1, 0);

    // Bước 1: Xây dựng Fenwick Tree từ mảng ban đầu
    build(initial_array, fenwick_tree, n);

    cout << "--- Fenwick Tree (1-based indexing) Minh Hoa ---" << endl;

    // Bước 2: Thực hiện các truy vấn tổng tiền tố ban đầu
    cout << "\n* Truy van tong tien to ban dau:" << endl;
    // Tổng từ index 1 đến 5: 1+2+3+4+5 = 15
    cout << "  Tong tien to den index 5 (sum(1..5)): " << query(5, fenwick_tree) << endl;
    // Tổng từ index 1 đến 10: 1+2+...+10 = 55
    cout << "  Tong tien to den index 10 (sum(1..10)): " << query(10, fenwick_tree) << endl;

    // Bước 3: Thực hiện truy vấn tổng đoạn ban đầu
    cout << "\n* Truy van tong doan ban dau:" << endl;
    // Tổng từ index 3 đến 7: 3+4+5+6+7 = 25
    cout << "  Tong doan tu index 3 den 7 (sum(3..7)): " << range_sum(3, 7, fenwick_tree) << endl; // query(7) - query(2) = (1+..+7) - (1+2) = 28 - 3 = 25

    // Bước 4: Thực hiện cập nhật tại một điểm
    int update_index_1 = 5;
    int update_value_1 = 10; // Thêm 10 vào giá trị tại index 5
    cout << "\n* Thuc hien cap nhat:" << endl;
    cout << "  Them " << update_value_1 << " vao phan tu tai index " << update_index_1 << endl;
    update(update_index_1, update_value_1, fenwick_tree, n); // arr[5] conceptual becomes 5 + 10 = 15

    // Bước 5: Thực hiện lại các truy vấn sau cập nhật
    cout << "\n* Truy van sau cap nhat dau tien:" << endl;
    // Tổng từ 1 đến 5: (1+2+3+4+5) + 10 = 15 + 10 = 25
    cout << "  Tong tien to den index 5 sau cap nhat: " << query(5, fenwick_tree) << endl;
    // Tổng từ 1 đến 10: (1+..+10) + 10 = 55 + 10 = 65
    cout << "  Tong tien to den index 10 sau cap nhat: " << query(10, fenwick_tree) << endl;
    // Tổng từ 3 đến 7: (3+4+5+6+7) + 10 = 25 + 10 = 35 (vì index 5 nằm trong đoạn [3, 7])
    cout << "  Tong doan tu index 3 den 7 sau cap nhat: " << range_sum(3, 7, fenwick_tree) << endl; // query(7) - query(2) = (original query(7) + 10) - original query(2) = (28+10) - 3 = 35

    // Bước 6: Thực hiện cập nhật thứ hai
    int update_index_2 = 2;
    int update_value_2 = -5; // Bớt 5 từ giá trị tại index 2
    cout << "\n* Thuc hien cap nhat thu hai:" << endl;
    cout << "  Them " << update_value_2 << " (bot 5) vao phan tu tai index " << update_index_2 << endl;
    update(update_index_2, update_value_2, fenwick_tree, n); // arr[2] conceptual becomes 2 - 5 = -3

    // Bước 7: Thực hiện lại các truy vấn sau cập nhật thứ hai
    cout << "\n* Truy van sau cap nhat thu hai:" << endl;
    // Tổng từ 1 đến 5: (Tổng sau update 1) - 5 = 25 - 5 = 20
    cout << "  Tong tien to den index 5 sau cap nhat thu 2: " << query(5, fenwick_tree) << endl;
     // Tổng từ 1 đến 3: (1+2+3 ban đầu) - 5 = 6 - 5 = 1 (vì index 2 nằm trong đoạn [1, 3])
     cout << "  Tong doan tu index 1 den 3 sau cap nhat thu 2: " << range_sum(1, 3, fenwick_tree) << endl; // query(3) - query(0). query(3) = (original query(3)) + delta at 2 = 6 + (-5) = 1. range_sum = 1 - 0 = 1.

    cout << "\n--- Ket thuc minh hoa ---" << endl;

    return 0;
}

Giải thích ví dụ:
- Chúng ta khởi tạo một mảng gốc initial_array (conceptually) và xây dựng fenwick_tree từ nó bằng hàm build.
- Sau đó, chúng ta thực hiện các truy vấn query và range_sum để kiểm tra tổng tiền tố và tổng đoạn ban đầu. Kết quả khớp với tính toán thủ công.
- Tiếp theo, chúng ta dùng hàm update để thêm 10 vào giá trị tại index 5. Hàm update này chỉ cần giá trị delta (sự thay đổi), không cần giá trị cũ.
- Sau khi cập nhật, chúng ta thực hiện lại các truy vấn. Các tổng tiền tố/đoạn bao gồm index 5 đã tăng thêm 10, chứng tỏ việc cập nhật đã được phản ánh đúng trong Fenwick Tree.
- Cuối cùng, chúng ta thực hiện thêm một cập nhật khác (thêm -5 vào index 2) và kiểm tra lại các tổng. Các tổng bị ảnh hưởng bởi index 2 cũng thay đổi tương ứng.

Ví dụ này minh họa cách Fenwick Tree duy trì tổng tiền tố một cách hiệu quả ngay cả sau khi có các cập nhật tại điểm.

Độ Phức Tạp

Thời gian: Cả thao tác update và query đều có độ phức tạp thời gian là O(log N), trong đó N là kích thước của mảng gốc. Điều này là do mỗi bước nhảy trong vòng lặp (index += index & (-index) hoặc index -= index & (-index)) tương ứng với việc di chuyển lên hoặc xuống một cấp trong cấu trúc cây nhị phân ngầm định, và chiều cao của cây này là log N. Thao tác range_sum chỉ là hai lần query, nên cũng là O(log N). Việc xây dựng cây ban đầu bằng cách lặp và update từng phần tử mất O(N log N).
Không gian: Fenwick Tree cần một mảng có kích thước O(N) để lưu trữ dữ liệu, tương tự kích thước mảng gốc.

So Sánh Ngắn Gọn với Segment Tree

Fenwick Tree và Segment Tree đều là những cấu trúc dữ liệu mạnh mẽ cho các bài toán về đoạn con.

Giống nhau: Cả hai đều cho phép truy vấn tổng đoạn và cập nhật điểm trong thời gian O(log N).
Khác nhau:
- Fenwick Tree thường đơn giản hơn để cài đặt cho các bài toán tổng tiền tố/tổng đoạn và cập nhật điểm cơ bản. Code ngắn gọn hơn.
- Segment Tree linh hoạt hơn, có thể dễ dàng mở rộng để xử lý các loại truy vấn khác ngoài tổng (ví dụ: min, max, GCD trên đoạn) và các loại cập nhật phức tạp hơn (ví dụ: cập nhật trên một đoạn - range update).
- Về hằng số, Fenwick Tree thường nhanh hơn một chút cho các thao tác cơ bản so với Segment Tree.

Bài tập ví dụ:

Nhà sư và những người bạn

Trong một buổi sinh hoạt tại hội trại, FullHouse Dev được giao một bài toán thú vị về một nhà sư và các học trò của mình. Với tinh thần ham học hỏi, nhóm đã bắt đầu tìm hiểu và giải quyết bài toán này.

Bài toán

Có một nhà sư đang đứng trước cửa lớp học của mình. Hiện tại trong lớp có $N$ học sinh, mỗi học sinh thứ $i$ có $A_i$ viên kẹo. Còn $M$ học sinh nữa sẽ vào lớp. Mỗi khi một học sinh mới vào, họ muốn ngồi cạnh một học sinh khác có chính xác cùng số kẹo với mình. Với mỗi học sinh, nhà sư sẽ trả lời "YES" nếu tìm được một bạn như vậy, và "NO" nếu không tìm được.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $T$ - số lượng test case.
Dòng đầu tiên của mỗi test case chứa hai số nguyên $N$ và $M$.
Dòng thứ hai chứa $N + M$ số nguyên, thể hiện số kẹo của các học sinh.

OUTPUT FORMAT:

Với mỗi test case, in ra $M$ dòng, mỗi dòng là câu trả lời của nhà sư.
In "YES" hoặc "NO" tương ứng với từng học sinh mới vào.

Ràng buộc:

$1 \leq T \leq 10$
$1 \leq N, M \leq 10^5$
$0 \leq A_i \leq 10^{12}$

Ví dụ

INPUT

1
2 3
3 2 9 11 2

OUTPUT

NO
NO
YES

Giải thích

Ban đầu trong lớp có học sinh với 3 và 2 viên kẹo.
Học sinh thứ nhất vào với 9 viên kẹo, không có ai trong lớp có 9 viên kẹo. Do đó: "NO"
Học sinh thứ hai vào với 11 viên kẹo, không có ai trong lớp có 11 viên kẹo. Do đó: "NO"
Học sinh thứ ba vào với 2 viên kẹo, đã có một bạn trong lớp có 2 viên kẹo. Do đó: "YES" Okay, đây là hướng dẫn giải bài toán "Nhà sư và những người bạn" bằng C++ một cách ngắn gọn và tập trung vào ý tưởng chính:

Hiểu yêu cầu: Bài toán yêu cầu với mỗi học sinh mới vào, kiểm tra xem đã có học sinh nào trong lớp (bao gồm cả N học sinh ban đầu và những học sinh mới đã vào trước đó) có chính xác cùng số kẹo hay không. Sau khi kiểm tra và in ra kết quả, học sinh mới này sẽ gia nhập lớp.
Xác định thao tác chính: Chúng ta cần một cách hiệu quả để:
- Lưu trữ số kẹo của tất cả học sinh đang có mặt trong lớp.
- Kiểm tra xem một số kẹo cụ thể có tồn tại trong tập hợp đang lưu trữ hay không.
- Thêm số kẹo của học sinh mới vào tập hợp.
Chọn cấu trúc dữ liệu: Để thực hiện kiểm tra sự tồn tại nhanh chóng (tìm kiếm), các cấu trúc dữ liệu dựa trên hashing hoặc cây tìm kiếm nhị phân cân bằng là phù hợp.
- set (trong C++): Duy trì các phần tử duy nhất theo thứ tự đã sắp xếp. Thao tác chèn (insert) và tìm kiếm (find) có độ phức tạp O(log K), trong đó K là số phần tử trong set.
- unordered_set (trong C++): Duy trì các phần tử duy nhất trong một bảng băm. Thao tác chèn và tìm kiếm có độ phức tạp trung bình O(1), trường hợp xấu nhất là O(K). Vì số lượng học sinh có thể lên tới $10^5$, cả hai cấu trúc này đều đủ hiệu quả. set cung cấp đảm bảo hiệu suất O(log K), trong khi unordered_set thường nhanh hơn trên thực tế (trung bình). Chọn set hoặc unordered_set. Do giá trị kẹo lớn ($10^{12}$), hãy sử dụng kiểu dữ liệu long long cho số kẹo và kiểu của set.
Thuật toán chi tiết:
- Đọc số test case T.
- Lặp T lần:
  - Đọc N và M.
  - Khởi tạo một set<long long> (hoặc unordered_set<long long>) để lưu số kẹo của các học sinh hiện có trong lớp.
  - Đọc N số kẹo đầu tiên từ input (đó là số kẹo của N học sinh ban đầu). Với mỗi số kẹo này, chèn nó vào set.
  - Lặp M lần (cho M học sinh mới):
    - Đọc số kẹo của học sinh mới này (gọi là current_candies).
    - Kiểm tra xem current_candies có tồn tại trong set hay không (sử dụng phương thức find hoặc count).
    - Nếu tìm thấy (find trả về iterator không phải end() hoặc count trả về > 0): In ra "YES".
    - Nếu không tìm thấy: In ra "NO".
    - Sau khi in ra kết quả, chèn current_candies vào set để học sinh này gia nhập lớp.
Lưu ý: Đảm bảo sử dụng long long cho biến lưu số kẹo và kiểu dữ liệu của set để chứa được giá trị lên đến $10^{12}$.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.