Trong quá trình học lập trình và đặc biệt là lập trình thi đấu, tôi đã gặp rất nhiều bài toán mà lời giải ngây thơ ban đầu chạy chậm đến mức không thể vượt qua giới hạn thời gian. Một trong những công cụ xuất hiện lặp đi lặp lại để giải quyết những bài toán như vậy là Fenwick Tree, còn được gọi là Binary Indexed Tree (BIT).
Điều thú vị là đây lại không phải là một cấu trúc dữ liệu thường được giảng dạy trong các môn học nhập môn ở trường đại học. Phần lớn chúng ta được học mảng, danh sách liên kết, hàng đợi, ngăn xếp, cây nhị phân, bảng băm,… nhưng Fenwick Tree thường chỉ xuất hiện khi bắt đầu tiếp xúc với thuật toán nâng cao hoặc lập trình thi đấu.
Trong bài viết này, tôi muốn chia sẻ cách tôi hiểu Fenwick Tree, tại sao nó hữu ích, cách nó hoạt động, và đặc biệt là cách áp dụng nó vào một bài toán thực tế mà ban đầu có độ phức tạp gần như không thể chạy được. Hy vọng bài viết sẽ giúp những người mới tiếp xúc với cấu trúc dữ liệu này có được một góc nhìn trực quan hơn.
Từ một bài toán chạy chậm
Đó là một bài toán trên Codeforces. Đề bài đầy đủ ở đây. Có thể tóm tắt đề bài như sau: Cho một mảng a có n phần tử tương ứng với n cột, giá trị mỗi phần tử là số lượng hộp của mỗi cột. Khi trượt tất cả các hộp sang phải nhất có thể, cần tính tổng quãng đường mà các hộp di chuyển. Ngoài ra, có thể bỏ đi một hộp trên cùng của cột bất kỳ. Cần tìm cách bỏ đi một hộp để tổng quãng đường là tối đa.
Sau khi phân tính bài toán, tôi tìm ra lời giải đơn giản như sau (sử dụng index bắt đầu từ 0 cho phù hợp với code). Bài toán có 2 phần, có thể tính toán riêng: tính tổng quãng đường các hộp di chuyển, tìm cách tối ưu việc bỏ đi một hộp ở cột bất kỳ.
Với phần thứ nhất, cần tính toán tổng quãng đường các hộp di chuyển. Với mỗi hộp ở cột thứ i, nó có thể di chuyển quãng đường tối đa là n - 1 -i (khi không có hộp nào bên phải nó cùng độ cao). Nếu ở cùng độ cao với nó, ở bên phải có c hộp, thì quãng đường nó di chuyển sẽ là n - 1 - i - c.
Để tính tổng quãng đường các hộp di chuyển, có thể duyệt mảng từ phải sang trái, dùng một mảng cnt để lưu số lượng các hộp đã duyệt ở từng độ cao. Code cho phần này như dưới đây:
int64_t ans = 0;
vector<int> cnt(ranges::max(a) + 1, 0);
for (int i = n - 1; i >= 0; i--) {
for (int h = 1; h <= a[i]; h++) {
ans += n - cnt[h] - 1 - i;
cnt[h]++;
}
}
Với phần thứ hai, do đã tính được tổng quãng đường các hộp di chuyển, lúc này chỉ cần tính việc bỏ đi một hộp ở cột bất kỳ mang lại bao nhiêu lợi ích mà thôi. Sau đó chúng ta sẽ chọn ra cột tối ưu nhất. Với cột thứ i, sau khi bỏ đi hộp trên cùng, giả sử độ cao của hộp này là h. Lúc này, tất cả các hộp ở cột bên trái cột i có độ cao h sẽ di chuyển được thêm 1 ô. Tức là với mỗi cột i, lợi ích nó mang lại khi bỏ đi hộp trên cùng là số lượng các cột j < i mà a[j] >= a[i].
int64_t d = 0, cur = 0;
for (int i = 0; i < n; i++) {
cur = 0;
for (int j = 0; j < i; j++) {
if (a[j] >= a[i]) cur += 1;
}
d = max(d, cur);
}
Cuối cùng là in ra kết quả tối ưu nhất:
cout << ans + d << '\n';
Tuy nhiên, với cách làm này, độ phức tạp là O(n² + n·maxA), với n tối đa là 2e5 thì cần tới hàng chục tỉ phép tính. Chắc chắn là không thể vượt qua được các bài test.
Tối ưu lời giải
Xem lại đoạn mã của phần thứ nhất, tôi tìm ra một công thức trông đơn giản hơn như sau. Hiểu đơn giản, cách làm là duyệt qua tất cả các cột từ trái sang phải, với mỗi cột i sẽ coi như các hộp đang được dồn lại ở cột i - 1. Lúc này các cột có độ cao lớn hơn a[i] có thể dịch chuyển được thêm 1 bước. Sau đó tiếp tục với các cột i + 1, i
+ 2, v.v…
int64_t ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
ans += max(0, a[j] - a[i]);
}
}
Tuy nhiên, độ phức tạp của đoạn mã này vẫn là O(n²). Trong lúc tìm cách tối ưu thuật toán, tôi biết đến Fenwick Tree.
Nhìn lại công thức tính toán, có thể thấy rằng với mỗi phần tử a[i], chúng ta cần tính tổng a[j] - a[i] với j < i và a[j] > a[i]. Công thức này có thể rút gọn thành tổng: Σa[j] - a[i] * số lượng phần
tử.
Như vậy nếu tôi biết được:
- Có bao nhiêu phần tử trước đó lớn hơn
a[i] - Tổng của các phần tử trước đó lớn hơn
a[i]
thì tôi sẽ tính được đóng góp của a[i].
Bài toán đã biến thành: Trong quá trình duyệt mảng từ trái sang phải, hãy liên tục trả lời truy vấn:
- Có bao nhiêu số lớn hơn
x? - Tổng các số lớn hơn
xlà bao nhiêu?
Đây chính là lúc Fenwick Tree xuất hiện.
Fenwick Tree là gì?
Fenwick Tree là một cấu trúc dữ liệu hỗ trợ:
- cập nhật một phần tử
- truy vấn tổng prefix
trong thời gian O(log n) thay vì O(n) như mảng thông thường.
Trực giác đầu tiên
Giả sử tôi có mảng:
1 2 3 4 5 6 7 8
Nếu muốn tính:
a[1] + a[2] + ... + a[8]
thì tôi cần cộng toàn bộ các phần tử.
Fenwick Tree lưu sẵn nhiều tổng trung gian:
[1]
[1..2]
[3]
[1..4]
[5]
[5..6]
[7]
[1..8]
Nhờ đó khi cần tính một prefix sum, tôi chỉ phải ghép vài khối lớn lại với nhau.
Đây là ý tưởng cốt lõi.
Cài đặt Fenwick Tree
Cập nhật
void add(int p, int v) {
for (; p <= n; p += p & -p) {
bit[p] += v;
}
}
Lấy prefix sum
int64_t sum(int p) {
int64_t res = 0;
for (; p > 0; p -= p & -p) {
res += bit[p];
}
return res;
}
Lấy tổng đoạn
sum(l, r) = sum(r) - sum(l - 1)
cài đặt:
int64_t sum(int l, int r) {
return sum(r) - sum(l - 1);
}
Tại sao lại là O(log n)?
Quan sát:
p += p & -p
hoặc:
p -= p & -p
Mỗi lần thực hiện sẽ loại bỏ bit thấp nhất của p. Số bit của một số nguyên cỡ:
log₂(n)
Nên tổng số bước chỉ là:
O(log n)
Ví dụ
Đây là một điểm rất hay khiến nhiều người mới học Fenwick Tree bị nhầm. Fenwick Tree không lưu trực tiếp theo kiểu:
id = 7
val = 10
ở đúng một vị trí.
Thay vào đó, giá trị được cộng vào nhiều node khác nhau để các node đó đại diện cho các đoạn (range) khác nhau. Giả sử:
index: 1 2 3 4 5 6 7 8
Các đoạn Fenwick:
bit[1] = [1]
bit[2] = [1..2]
bit[3] = [3]
bit[4] = [1..4]
bit[5] = [5]
bit[6] = [5..6]
bit[7] = [7]
bit[8] = [1..8]
Khi cộng:
add(7, 10)
các đoạn bị ảnh hưởng là:
[7]
[1..8]
nên:
bit[7] += 10
bit[8] += 10
Những node này đại diện cho đoạn nào?
Một node Fenwick:
bit[i]
đại diện cho đoạn:
[i-lowbit(i)+1, i]
Ví dụ: bit[7]
lowbit(7)=1
Đại diện:
[7, 7]
bit[8]
lowbit(8)=8
Đại diện:
[1, 8]
Nên sau khi:
add(7, 10);
ta đang nói rằng:
Mọi đoạn chứa vị trí 7 đều phải biết rằng vị trí 7 tăng thêm 10.
Query thì sao?
Giả sử gọi:
sum(7)
Ta thực hiện:
7 -> 6 -> 4 -> 0
vì:
p -= p & -p;
Các node được cộng vào kết quả:
bit[7]
bit[6]
bit[4]
tương ứng các đoạn:
[7]
[5..6]
[1..4]
Ghép lại:
[1..7]
Chính là prefix sum cần tìm.
Một cách nhớ rất dễ
Khi:
add(pos, val)
ta đi lên trên:
pos += lowbit(pos)
để thông báo cho tất cả các đoạn lớn hơn chứa pos.
Khi:
sum(pos)
ta đi xuống dưới:
pos -= lowbit(pos)
để ghép các đoạn nhỏ lại thành:
[1..pos]
Ví dụ với:
add(7, 10)
Fenwick thực sự lưu:
bit[7] += 10
bit[8] += 10
chứ không chỉ lưu riêng ở:
bit[7]
Đó chính là bí quyết giúp Fenwick trả lời truy vấn prefix sum trong O(log n) thay vì O(n).
Coordinate Compression
Trong rất nhiều bài toán, giá trị không nhỏ.
Ví dụ:
a = {100, 1000000, 7}
Không thể tạo Fenwick Tree kích thước:
1000000
chỉ để lưu ba giá trị.
Ta thực hiện nén tọa độ.
Ví dụ:
a = {100, 1000000, 7}
Sau khi sắp xếp:
vals = {7, 100, 1000000}
Gán:
7 -> 1
100 -> 2
1000000 -> 3
Tất cả truy vấn sau đó được thực hiện trên:
1..3
Áp dụng vào bài toán
Ta cần:
Σ(a[j]-a[i])
với:
j < i
a[j] > a[i]
Khi đang xét:
x = a[i]
Tôi muốn biết:
count_gt
và
sum_gt
Fenwick thứ nhất: đếm số phần tử
Tôi tạo:
Fenwick bit_cnt;
Mỗi lần gặp một giá trị:
bit_cnt.add(id, 1);
Khi cần biết:
có bao nhiêu số lớn hơn x
ta truy vấn:
cnt_gt
=
bit_cnt.query(id + 1, m);
Fenwick thứ hai: tổng các giá trị
Tôi tạo:
Fenwick bit_sum;
Mỗi lần thêm:
bit_sum.add(id, x);
Truy vấn:
sum_gt
=
bit_sum.query(id + 1, m);
Tính đóng góp của một phần tử
Ví dụ:
Các số trước đó:
8 10 6
x = 5
Khi đó:
count_gt = 3
sum_gt = 24
Đóng góp là:
24 - 3 * 5 = 9
vì:
(8 - 5) + (10 - 5) + (6 - 5) = 9
Tối ưu hóa việc loại bỏ 1 hộp
Đoạn mã gốc của phần này như sau:
for (int j = 0; j < i; j++) {
if (a[j] >= a[i]) {
cur++;
}
}
Mục tiêu là đếm:
bao nhiêu phần tử trước đó >= a[i]
Đây cũng là bài toán mà Fenwick tree có thể giải quyết, tương tự như phần trước. Thậm chí phần này có thể kết hợp tính toán luôn trong cùng một vòng lặp với phần trước.
Dưới đây là lời giải đầy đủ cho bài toán này:
/*!
* author: manhhomienbienthuy
* created: 2026-07-09T00:53:15+00:00
* https://codeforces.com/contest/2227/problem/F
*/
#include <bits/stdc++.h>
using namespace std;
struct fenwick {
int n;
vector<int64_t> bit;
fenwick(int n_) : n(n_), bit(n + 1, 0) {}
void add(int p, int64_t v) {
for (; p <= n; p += p & -p) {
bit[p] += v;
}
}
int64_t sum(int p) const {
int64_t res = 0;
for (; p > 0; p -= p & -p) {
res += bit[p];
}
return res;
}
int64_t sum(int l, int r) const { return sum(r) - sum(l - 1); }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;
vector<int> vals = a;
ranges::sort(vals);
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = (int)vals.size();
auto gid = [&](int x) {
return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()) + 1;
};
fenwick bit_cnt(m);
fenwick bit_sum(m);
int64_t ans = 0, d = 0;
for (int x : a) {
int id = gid(x);
int64_t cnt_gt = bit_cnt.sum(id + 1, m);
int64_t sum_gt = bit_sum.sum(id + 1, m);
ans += sum_gt - cnt_gt * x;
d = max(d, bit_cnt.sum(id, m));
bit_cnt.add(id, 1);
bit_sum.add(id, x);
}
cout << ans + d << '\n';
}
return 0;
}
Những trường hợp nào nên dùng Fenwick Tree?
Sau một thời gian giải thuật toán, tôi thấy Fenwick Tree thường xuất hiện trong các tình huống sau.
Đếm nghịch thế (Inversion Count)
Bài toán kinh điển:
Có bao nhiêu cặp:
i < j
a[i] > a[j]
Fenwick Tree giải trong:
O(n log n)
Truy vấn tần suất
Ví dụ:
Đã xuất hiện bao nhiêu số <= x ?
Truy vấn thứ hạng
Ví dụ:
x hiện là số nhỏ thứ mấy?
Dynamic Order Statistics
Một số bài toán yêu cầu:
thêm
xóa
đếm
liên tục.
Fenwick Tree thường là lời giải đơn giản hơn Segment Tree.
Đếm số lượng trong đoạn
Ví dụ:
Có bao nhiêu phần tử thuộc [L,R]?
Tính tổng trọng số
Giống bài toán ở trên:
Tổng các giá trị lớn hơn x là bao nhiêu?
Kinh nghiệm cá nhân
Tôi từng mất khá nhiều thời gian để hiểu vì sao một cấu trúc dữ liệu ngắn như Fenwick Tree lại được dùng nhiều đến vậy. Sau đó tôi nhận ra rằng giá trị lớn nhất của nó không nằm ở vài dòng mã nguồn, mà nằm ở cách biến đổi bài toán.
Một bài toán ban đầu có vẻ yêu cầu duyệt:
mọi cặp phần tử
thường sẽ trở thành:
đếm + tính tổng
trên các phần tử đã xuất hiện.
Ngay khi nhìn thấy dạng này, Fenwick Tree gần như là công cụ đầu tiên tôi nghĩ tới.
Kết luận
Fenwick Tree là một cấu trúc dữ liệu đơn giản nhưng cực kỳ mạnh mẽ. Chỉ với khả năng cập nhật một điểm và truy vấn tổng prefix trong O(log n), nó có thể giải quyết rất nhiều bài toán đếm, thống kê, nghịch thế, xếp hạng và truy vấn động.
Trong bài toán ví dụ của bài viết, chúng ta đã biến một lời giải có độ phức tạp:
O(n² + n·maxA)
thành:
O(n log n)
bằng cách sử dụng hai Fenwick Tree để lưu số lượng phần tử và tổng giá trị của các phần tử đã xuất hiện.
Đối với tôi, Fenwick Tree là một trong những cấu trúc dữ liệu đem lại “cảm giác khai sáng” rõ rệt nhất khi học thuật toán. Nó đơn giản hơn Segment Tree, dễ cài đặt hơn nhiều cấu trúc nâng cao khác, nhưng lại đủ mạnh để xuất hiện trong vô số bài toán thực tế và bài toán thi đấu. Nếu bạn mới làm quen với các kỹ thuật tối ưu truy vấn trên mảng, đây là một cấu trúc dữ liệu rất đáng để đầu tư thời gian tìm hiểu kỹ.
