Tác giả:
Reviewer:
Cây chỉ số nhị phân (tên tiếng Anh là Binary Indexed Tree) hay cây Fenwick là một cấu trúc dữ liệu được sử dụng khá phổ biến trong lập trình thi đấu vì có thể cài đặt nhanh, dễ dàng so với các CTDL khác.
Cho mảng gồm phần tử (đánh số từ ). Có truy vấn thuộc 2 loại:
Giới hạn:
Với truy vấn loại 1, ta đơn thuần tăng phần tử thêm .
Với truy vấn loại 2, ta duyệt qua tất cả phần tử trong đoạn và cộng giá trị vào biến kết quả.
const int N = 200003;
int a[N];
void update(int u, int x) {
a[u] = a[u] + x;
}
int getSum(int p) {
int ans = 0;
for (int i = 1; i <= p; ++i)
ans = ans + a[i];
return ans;
}
Đối chiếu giới hạn, cách "ngây thơ" trên tỏ ra chậm chạp, không đủ để xử lí yêu cầu bài toán.
Nhận thấy đây là một dạng của bài toán Range Sum Query, ta có thể áp dụng mảng cộng dồn (prefix sum) để tính nhanh tổng một đoạn.
Khi cập nhật giá trị một phần tử, ta đồng thời cập nhật tất cả các prefix chứa phần tử đó.
int sum[N];
void preprocess() {
sum[1] = a[1];
for (int i = 2; i <= n; ++i) {
sum[i] = sum[i - 1] + a[i];
}
}
void update(int u, int x) {
for (int i = u; i <= n; ++i) {
sum[i] = sum[i] + x;
}
}
int getSum(int p) {
return sum[p];
}
Nếu bài toán không có truy vấn cập nhật, độ phức tạp là , đủ nhanh để giải quyết. Tuy nhiên, khi có thao tác cập nhật, độ phức tạp bị đẩy lên - tương đương với độ phức tạp của cách ngây thơ 1.
Để có thể giải quyết bài toán một cách hiệu quả, ta cần một CTDL có thể sử dụng tính chất prefix sum để trả về kết quả nhanh, đồng thời có thể nhanh chóng cập nhật giá trị cho prefix.
Cấu trúc prefix sum được biểu diễn qua sơ đồ sau:
Nhận xét: Mỗi phần tử chứa tổng của tất cả phần tử từ ; vì thế, phần tử sẽ chứa phần tử nếu thỏa , số phần tử cần cập nhật là , gần tương đương độ dài của mảng.
Để tăng tốc độ cập nhật phần tử, cần bố trí lại phạm vi của từng đoạn gắn với để cực tiểu số phần tử cần cập nhật nhưng vẫn phải đảm bảo tính liên tục để áp dụng tính chất của prefix sum.
Mỗi chỉ số đều có thể biểu diễn bằng tổng của các lũy thừa cơ số , vì thế, để tính tổng của các phần tử thuộc , ta có thể tách đoạn này thành các đoạn nhỏ hơn có độ dài và cộng lại tổng tính được trên từng đoạn.
Cụ thể, đặt . Để tính tổng từ , ta tính tổng các phần tử thuộc đoạn , sau đó tính tiếp tổng của đoạn , lặp lại quá trình này cho đến khi ta đến đoạn cuối cùng là . có thể có tối đa bits, vì thế độ phức tạp khi tính tổng theo cách này là , trong đó là độ phức tạp khi lấy tổng một đoạn.
Từ cách chia block trên, ta quan sát được rằng block cuối cùng đối với mỗi (là block tổng chứa phần tử ở chỉ số ) có độ dài bằng với bit nhỏ nhất trong biểu diễn nhị phân của . Đây chính là ý tưởng của cây BIT, ta sẽ lưu thông tin về block cuối của từng phần tử và thực hiện thao tác truy vấn trên đấy.
Dưới đây là hình ảnh minh họa cây BIT:
Trong hình trên, những đoạn được tô đậm là đoạn của phần tử chỉ số được BIT lưu trữ; những đoạn được tô nét mảnh không được lưu trữ trực tiếp mà sẽ được truy cập gián tiếp.
Mặc dù có bản chất là cây, tính chất ở trên cho phép chúng ta lưu trữ BIT dưới dạng một mảng đơn giản có độ dài bằng với độ dài mảng ta đang làm việc.
int bit[N];
Để tìm tổng các phần tử trong đoạn , ta sẽ lần lượt đi qua tất cả bit của theo giá trị tăng dần. Mỗi lần đi qua , ta sẽ cộng vào kết quả hiện tại, rồi trừ đi bit nhỏ nhất của khỏi chính nó; quá trình lặp lại cho đến khi .
Để lấy bit nhỏ nhất của một số , ta có thể sử dụng công thức n & ~(n - 1)
được đề cập tại bài tại đây. Khi thao tác bit với số âm, C++ sử dụng phép bù 2: ~n = - n - 1
; vì vậy ta có phép biến đổi: n & ~(n - 1) = n & (-(n - 1) - 1) = n & (-n)
dễ sử dụng hơn.
int getSum(int p) {
int idx = p, ans = 0;
while (idx > 0) {
ans += bit[idx];
idx -= (idx & (-idx));
}
return ans;
}
Độ phức tạp khi truy vấn tổng: .
Để cập nhật phần tử tại vị trí , ta sẽ thực hiện quá trình ngược lại so với khi truy vấn tìm tổng: cộng bit nhỏ nhất vào cho đến khi vượt ngoài biên của mảng.
void update(int u, int v) {
int idx = u;
while (idx <= n) {
bit[idx] += v;
idx += (idx & (-idx));
}
}
Chứng minh tính đúng đắn của thuật trên như sau: mỗi khi ta cộng thêm 1 lượng bằng với ( là bit nhỏ nhất của ) thì đoạn dịch qua phải một lượng thành (do bit nhỏ nhất lúc này vẫn có thể tính là ). Đồng thời lúc đó, bit nhỏ nhất tăng ít nhất 2 lần do (mới cộng thêm) + (có sẵn trong u) tạo thành làm cho biên trái dịch trái ít nhất lần thành (nếu có sẵn trong thì tiếp tục gộp lại làm bit nhỏ nhất tăng lên là , ...), do đó biên trái luôn được giữ <= biên ban đầu.
Mỗi lần cộng thêm, bit cuối luôn bị dịch lên ít nhất 1 lần, dẫn đến có tối đa lần dịch bit. Vì thế độ phức tạp khi cập nhật là .
Bằng cây chỉ số nhị phân (BIT), ta dễ dàng tính được prefix sum và cập nhật giá trị chỉ trong , mặt khác so với các CTDL khác, BIT dễ dàng cài đặt hơn rất nhiều và không tốn quá nhiều thời gian để code.
Quay lại bài toán đầu, nếu chúng ta thay đổi yêu cầu thành tìm tổng trên đoạn , tính chất của prefix sum dễ dàng cho ta tìm được kết quả thông qua phép . Tuy nhiên, không phải tất cả phép toán nào đều cho phép chúng ta dễ dàng lấy kết quả thông qua phép hiệu như vậy. Đối với các phép , không tồn tại phép hiệu cho ta phép lấy kết quả của một đoạn dễ dàng, vì thế ta không thể áp dụng BIT đối với những bài toán loại này.
Đây là một khuyết điểm mấu chốt của BIT, vì thế cần nắm rõ tính chất và những bài toán để quyết định có nên sử dụng BIT không.
Ta thay đổi nội dung bài toán ban đầu như sau:
Ta có thể cài đặt "ngây thơ" bằng cách áp dụng hàm update()
trên tất cả phần tử cần được cập nhật, độ phức tạp khi này là . Dĩ nhiên cách này quá chậm, đòi hỏi ta cần tìm một cách cập nhật đoạn một cách nhanh hơn để giữ nguyên độ phức tạp .
Mảng hiệu (difference array) là một loại mảng lưu hiệu giữa các phần tử liền kề với nhau.
Mảng hiệu được xây dựng bằng cách sau:
Bạn có thể theo dõi hình dưới và code minh họa để hiểu rõ hơn:
int diff[N + 1];
diff[1] = a[1];
for (int i = 2; i <= n; ++i) {
diff[i] = a[i] - a[i - 1];
// lấy phần tử thứ i trừ cho phần tử trước nó
}
Khi cộng tất cả phần tử từ đến , ta có:
Từ tính chất này, khi tính được mảng hiệu, để tính được giá trị của ta chỉ cần lấy tổng của phần tử đầu tiên. Khi này, bài toán của chúng ta thực chất được đưa về tính tổng trên mảng , vấn đề hiện tại là thao tác update()
cần được xử lí như thế nào.
Hình dưới đây minh họa thao tác cập nhật trên một đoạn - từ mảng trên, ta cộng vào đoạn :
Khi cập nhật, do các phần tử liền kề trong đoạn đều được cộng cùng một giá trị nên hiệu giữa chúng thực chất vẫn không đổi. Khác biệt duy nhất khi cập nhật nằm ở 2 biên của đoạn: giữa và ; vì thế ta chỉ cần cập nhật điểm tại 2 biên trên mảng hiệu và dùng truy vấn lấy tổng để tính giá trị hiện tại của .
void updatePoint(int u, int v) {
int idx = u;
while (idx <= n) {
bit[idx] += v;
idx += (idx & (-idx));
}
}
void updateRange(int l, int r, int v) {
updatePoint(l, v);
updatePoint(r + 1, -v);
}
int get(int u) {
int idx = u, ans = 0;
while (idx > 0) {
ans += bit[idx];
idx -= (idx & (-idx));
}
return ans;
}
Hình trên sẽ giúp ta minh họa trực quan hơn mối quan hệ về tổng các phần tử với mảng và mảng hiệu .
Nhắc lại: . Dựa vào hình, ta có thể tính lần lượt tổng các phần tử từ đến như sau:
Tuy nhiên, do sự biến động của hệ số khi nhân nên cách này không thuận tiện khi ta phải truy vấn liên tục. Để dễ dàng hơn, ta sẽ cố định mỗi nhân với hệ số , khi này:
Tóm lại, ta thu được:
Cả hai giá trị và đã được đơn giản hóa, lúc này ta chỉ cần lưu toàn bộ giá trị vào mảng và vào mảng và dựng mảng cộng dồn trên hai mảng đó.
Thao tác cập nhật trên mảng giống với thao tác cập nhật đã đề cập ở trên, còn ở mảng thì khác biệt duy nhất là việc xử lý nhân hệ số . Tuy vậy, hệ số trên không đổi trong quá trình tính toán với từng phần tử nên ta chỉ cần nhân hệ số này với giá trị cần cập nhật và áp dụng phương thức tương tự như ở cập nhật trên .
Code tham khảo:
vector<int> bit1, bit2;
/*
Các hàm update và sum cần làm việc trên một trong hai BIT riêng biệt.
Sử dụng vector cho phép truyền BIT vào làm việc trực tiếp dễ dàng hơn.
*/
void updatePoint(vector<int>& b, int u, int v) {
int idx = u;
while (idx <= n) {
b[idx] += v;
idx += (idx & (-idx));
}
}
void updateRange(int l, int r, int v) {
updatePoint(bit1, l, (n - l + 1) * v);
updatePoint(bit1, r + 1, -(n - r) * v);
updatePoint(bit2, l, v);
updatePoint(bit2, r + 1, -v);
}
int getSumOnBIT(vector<int>& b, int u) {
int idx = u, ans = 0;
while (idx > 0) {
ans += b[idx];
idx -= (idx & (-idx));
}
return ans;
}
int prefixSum(int u) {
return getSumOnBIT(bit1, u) - getSumOnBIT(bit2, u) * (n - u);
}
int rangeSum(int l, int r) {
return prefixSum(r) - prefixSum(l - 1);
}
VNOI Online Judge có phân loại riêng các bài tập về BIT, các bạn có thể tham khảo tại đây.