I. Giới Thiệu Chung

Trong lập trình, việc xử lý các truy vấn trên đoạn luôn là một trong những chủ đề thú vị và quan trọng, nhất là trong các kỳ thi lập trình. Một trong những cấu trúc dữ liệu phổ biến để xử lý vấn đề này là Cây Phân Đoạn (Segment Tree). Tuy nhiên, cây phân đoạn có nhược điểm lớn là yêu cầu bộ nhớ cao và các thao tác phức tạp hơn như Lazy Propagation trong trường hợp cần cập nhật trên đoạn.

Để giải quyết vấn đề này, chúng ta có thể sử dụng cấu trúc dữ liệu đơn giản hơn, mang tên Cây Nhị Phân Chỉ Số (Binary Indexed Tree). Cấu trúc này không chỉ đơn giản hơn mà còn rất hiệu quả cho các bài toán liên quan đến cập nhật và tính tổng các đoạn, điều này làm cho nó trở thành một lựa chọn yêu thích trong lập trình.

II. Bài Toán Cơ Sở

Cùng xem xét bài toán sau:
Cho mảng số nguyên AAA gồm n phần tử a1, a2, …, an. Bạn cần trả lời Q truy vấn thuộc hai loại:

• 1 u v: Cộng thêm vào phần tử a_u giá trị v.
• 2 p: Tính tổng các phần tử a1, a2, …, a_p.

Yêu cầu: Hãy trả lời các truy vấn loại 2 và đưa ra kết quả.

Input:

• Dòng đầu tiên chứa hai số nguyên dương n và Q.
• Dòng thứ hai chứa n số nguyên a1, a2, …, an.
• Q dòng tiếp theo, mỗi dòng gồm: Số đầu tiên là 1 hoặc 2 thể hiện loại truy vấn, theo sau là hai số u, v hoặc số p.

Ràng buộc:

• 1 ≤ n ≤ 10^5, 1 ≤ Q ≤ 10^5.
• 1 ≤ u ≤ n; 1 ≤ v ≤ 10^4.
• 1 ≤ p ≤ n.

Lời Giải Ngây Thơ

Cách 1

Với truy vấn loại 1, ta có thể tăng a_u lên v với mỗi truy vấn, còn với truy vấn loại 2, ta sẽ duyệt qua tất cả các phần tử từ a1 đến a_p và tính tổng.

void update(int u, int v, int n, vector<int> &a) {
    a[u] += v;
}

int get_sum(int p, vector<int> &a) {
    return accumulate(a.begin() + 1, a.begin() + p + 1, 0);
}

Tuy nhiên, độ phức tạp tổng quát của phương pháp này lên tới O(n × Q), không phù hợp với ràng buộc của bài toán.

Cách 2

Sử dụng mảng tổng tiền tố sẽ giúp truy vấn tổng trong O(1), nhưng cần cập nhật lại mảng tổng khi có thay đổi, dẫn đến độ phức tạp O(Q × n).

III. Cây Nhị Phân Chỉ Số (Binary Indexed Tree)

1. Cải Tiến Truy Vấn Và Cập Nhật

Thay vì lưu tất cả dữ liệu, chúng ta có thể sử dụng một mảng để lưu trữ thông tin về các đoạn. Mỗi phần tử trong mảng sẽ lưu tổng các giá trị từ 1 đến một chỉ số nào đó, theo cách sao cho khi cập nhật một phần tử, chỉ cần cập nhật một mức tối thiểu các phần tử khác, dựa trên tính chất các lũy thừa của số 2.

2. Cài Đặt BIT

Chúng ta có thể cài đặt Cây Nhị Phân Chỉ Số dưới dạng một mảng có độ dài đúng bằng chiều dài của mảng đang làm việc.

vector<int> bit(n + 1);

Thao Tác Tìm Tổng

Để tìm tổng các phần tử trong đoạn [1,p], ta sẽ lặp qua tất cả các bit của p từ phải qua trái.

int get_sum(int p, vector<int> &bit) {
    int id = p, sum = 0;
    while (id > 0) {
        sum += bit[id];
        id -= (id & (-id));
    }
    return sum;
}

Thao Tác Cập Nhật

Thao tác cập nhật trên Cây Nhị Phân Chỉ Số cũng tương tự, ta sẽ cộng giá trị cho một vị trí nhất định và cập nhật các vị trí liên quan.

void update(int u, int v, int n, vector<int> &bit) {
    int id = u;
    while (id <= n) {
        bit[id] += v;
        id += (id & (-id));
    }
}

IV. Kết Luận

Cây Nhị Phân Chỉ Số là một công cụ hữu ích để giải quyết các bài toán liên quan đến truy vấn và cập nhật mảng. So với Cây Phân Đoạn, BIT tiện lợi hơn cho nhiều bài toán đơn giản. Tuy nhiên, mỗi cấu trúc dữ liệu lại có những ưu điểm và hạn chế riêng, vì vậy cần cân nhắc kỹ lưỡng trong từng trường hợp cụ thể.
source: viblo