Fenwick tree - Cây chỉ số nhị phân (Binary Indexed Tree)
Contents
Fenwick Tree, hay còn gọi là cây chỉ số nhị phân (Binary Indexed Tree - BIT), là một cấu trúc dữ liệu tối ưu cho việc cập nhật giá trị một phần tử và tìm tổng, min/max giữa 2 vị trí bất kì trong mảng. Độ phức tạp cho mỗi lần cập nhật, truy xuất là \(O(\log N)\) với N là độ dài dãy cần quản lý. Ngoài thao tác tính tổng, tìm min/max thì BIT còn có thể sử dụng được cho nhiều thao thác khác nữa.
BIT là một cây, tuy nhiên trong phạm vi bài viết này sẽ không đề cập tới khái niệm gốc hoặc chứng minh tính đúng đắn của nó, mà chỉ dừng lại ở mức kiến thức đủ để cài đặt và sử dụng trong thực tế.
Bài toán
Cho dãy số A có N phần tử, giá trị ban đầu của các phần tử bằng 0. Có 2 loại truy vấn cần thực hiện:
- Tăng \(A(i)\) lên một đơn vị
- Tính tổng của mảng từ \(A(1)\) đến \(A(i)\).
Nếu sử dụng cách tính tổng như bình thường thì thao tác cập nhật có độ phức tạp là \(O(1)\), còn thao tác tính tổng có độ phức tạp \(O(N)\).
Nếu sử dụng BIT cho bài này thì cả 2 thao tác có chung độ phức tạp là \(O(\log N)\).
Định nghĩa BIT
Xem BIT như một mảng F có N phần tử, đánh số từ 1. \(F(i)\) lưu tổng của i & (-i) phần tử, bắt đầu từ \(A(i)\)
ngược về \(A(1)\). Tức là \(F(i)\) lưu tổng từ A(i-(i&-i)+1) đến A(i).
Giải thích phép tính i & (-i):
i & (-i) sẽ trả về bit đầu tiên khác 0 của i, ví dụ \(i = 20\), có biểu diễn nhị phân là \(10100\), thì i & (-i)
sẽ có biểu diễn nhị phân là \(100\), tức là 20 & (-20) = 4.
Ví dụ mảng A có 10 phần tử và cây BIT tương ứng:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| A | 3 | 2 | 1 | 5 | 3 | 6 | 2 | 0 | 7 | 1 |
| F | 3 | 5 | 1 | 11 | 3 | 9 | 2 | 22 | 7 | 8 |
Thao tác truy xuất
Để tính tổng từ \(A(1)\) đến \(A(i)\), ta lặp như sau:
result = 0
while i >= 1:
result = result + F[i]
i = i - (i & -i)
Có thể thấy, sau mỗi lần lặp thì một bit 1 trong \(i\) sẽ bị loại bỏ, vì thế số lần lặp là số lượng bit 1 của \(i\), dẫn đến độ phức tạp là \(O(\log N)\).
Cách trên cho phép tính tổng từ đầu dãy đến \(A(i)\), nếu muốn tính tổng trên một đoạn từ \(A(j)\) đến \(A(i)\) thì phải thay đổi thao tác trên một ít:
result = 0
while i >= j:
if i - (i & -i) >= j:
result = result + F[i]
i = i - (i & -i)
else:
result = result + A[i]
i = i - 1
Thao tác cập nhật
Trong truy vấn cập nhật, ta cần tăng giá trị của \(A(i)\) lên 1, vì vậy ta cũng
cần phải tăng các giá trị \(F(j)\) mà trong dãy tổng của \(F(j)\) có chứa \(A(i)\). Để làm được điều này,
chỉ cần làm ngược lại với thao tác truy xuất bên trên, tức là i = i + (i & -i).
Đoạn code cập nhật như sau:
while i <= n:
F[i] = F[i] + 1
i = i + (i & -i)