Nếu phải chọn một cấu trúc dữ liệu khiến tôi trì hoãn việc học lâu nhất trong những năm đầu làm quen với competitive programming, có lẽ tôi sẽ chọn Segment Tree. Tôi đã nghe nhắc đến nó không biết bao nhiêu lần trong editorial, trong các buổi thảo luận thuật toán, hay trong những bài giải của các cao thủ trên Codeforces. Thế nhưng mỗi lần mở mã nguồn của một Segment Tree ra xem, tôi đều có cảm giác như đang nhìn vào một thứ gì đó quá phức tạp. Mãi đến sau này, khi thực sự ngồi xuống tìm hiểu một cách nghiêm túc, tôi mới nhận ra rằng Segment Tree không đáng sợ như mình từng nghĩ. Trong bài viết này, tôi muốn chia sẻ lại hành trình học Segment Tree của bản thân, từ những khó khăn ban đầu cho đến cách tôi dần hiểu được bản chất của cấu trúc dữ liệu này.
Vì sao tôi cần học Segment Tree?
Tôi không học Segment Tree vì tò mò về một cấu trúc dữ liệu mới. Lý do thực tế hơn rất nhiều. Trong quá trình giải các bài toán competitive programming, tôi liên tục gặp những trường hợp mà các kỹ thuật quen thuộc của mình không còn đủ sức giải quyết trong giới hạn thời gian của đề bài.
Một dạng bài xuất hiện rất thường xuyên là làm việc với một mảng và xử lý số lượng lớn truy vấn trên mảng đó. Những truy vấn này thường bao gồm hai nhóm thao tác quen thuộc: cập nhật dữ liệu và truy vấn thông tin trên một đoạn.
Ví dụ, đề bài có thể cho một mảng gồm n phần tử và yêu cầu xử lý q truy vấn như sau:
- Cập nhật giá trị tại một vị trí bất kỳ.
- Tính tổng các phần tử trong đoạn
[l, r].
Khi mới gặp dạng bài này, tôi nghĩ đến cách giải trực tiếp nhất. Nếu cần tính tổng trên đoạn [l, r], tôi chỉ việc duyệt qua toàn bộ các phần tử trong đoạn đó rồi cộng lại.
int64_t sum = 0;
for (int i = l; i <= r; i++) sum += a[i];
Cách làm này hoàn toàn ổn nếu dữ liệu nhỏ. Tuy nhiên, competitive programming hiếm khi cho chúng ta những bộ dữ liệu dễ chịu như vậy. Nếu đề bài có:
n = 200000
q = 200000
thì mỗi truy vấn mất O(n) đồng nghĩa với tổng thời gian thực hiện có thể lên tới hàng chục tỷ phép tính. Trong những trường hợp như vậy, kết quả gần như chắc chắn là TLE.
Đó là thời điểm tôi bắt đầu nhận ra rằng cần phải tìm một cách nhìn khác về dữ liệu. Thay vì chấp nhận việc truy vấn luôn phải duyệt lại toàn bộ đoạn, có lẽ phải tồn tại một phương pháp nào đó giúp tái sử dụng các kết quả đã tính trước.
Prefix Sum có giải quyết được vấn đề không?
Khi lần đầu học Prefix Sum, tôi đã từng nghĩ rằng đây chính là lời giải hoàn hảo cho mọi bài toán tính tổng trên đoạn.
Ý tưởng của Prefix Sum rất đẹp và dễ hiểu. Thay vì tính tổng lại từ đầu cho mỗi truy vấn, tôi lưu sẵn tổng tích lũy:
prefix[i] = prefix[i - 1] + a[i];
Khi cần tính tổng đoạn [l, r], tôi chỉ việc lấy:
sum(l, r) = prefix[r] - prefix[l - 1];
Toàn bộ quá trình truy vấn chỉ tốn O(1).
Lần đầu tiên sử dụng Prefix Sum, tôi thực sự có cảm giác mình vừa học được một “chiêu thức bí mật”. Những bài toán trước đây mất hàng giây để chạy bỗng trở nên nhanh hơn rất nhiều.
Tuy nhiên, niềm vui đó không kéo dài được lâu.
Rất nhiều đề bài không chỉ yêu cầu truy vấn mà còn yêu cầu cập nhật dữ liệu.
Ví dụ:
a[100] = 123
Sau khi thay đổi giá trị tại vị trí 100, toàn bộ các giá trị Prefix Sum phía sau đều không còn chính xác nữa. Muốn cập nhật đúng, tôi phải tính lại từ vị trí 100 đến cuối mảng.
Nói cách khác, một thao tác cập nhật lại tốn O(n).
Lúc này tôi mới nhận ra rằng Prefix Sum chỉ thực sự mạnh trong những bài toán mà dữ liệu không thay đổi hoặc thay đổi rất ít. Khi truy vấn và cập nhật cùng xuất hiện với tần suất lớn, Prefix Sum không còn là giải pháp phù hợp nữa.
Chính tại đây tôi bắt đầu hiểu vì sao Segment Tree được tạo ra. Nó xuất hiện để lấp vào khoảng trống giữa hai thế giới:
- Mảng thông thường: cập nhật nhanh nhưng truy vấn chậm.
- Prefix Sum: truy vấn nhanh nhưng cập nhật chậm.
Segment Tree cố gắng giữ cho cả hai thao tác đều đủ nhanh.
Segment Tree là gì?
Trong những lần đầu đọc tài liệu, tôi thường bắt gặp định nghĩa như sau:
Segment Tree là cấu trúc dữ liệu dùng để lưu trữ thông tin trên các đoạn của mảng.
Định nghĩa này hoàn toàn chính xác, nhưng thú thật là nó không giúp tôi hình dung được nhiều.
Sau một thời gian loay hoay, tôi tự diễn giải lại bằng ngôn ngữ của riêng mình:
Thay vì chỉ lưu thông tin của từng phần tử riêng lẻ, Segment Tree lưu thông tin tổng hợp của rất nhiều đoạn khác nhau trong cùng một mảng.
Giả sử tôi có mảng:
1 3 5 7 9 11
Segment Tree sẽ chia mảng thành những đoạn nhỏ hơn:
[1,6]
├─ [1,3]
│ ├─ [1,2]
│ └─ [3,3]
└─ [4,6]
├─ [4,5]
└─ [6,6]
Mỗi nút trong cây đại diện cho một đoạn liên tiếp của mảng.
Điều quan trọng là mỗi nút không chỉ lưu đoạn mà còn lưu một giá trị tổng hợp của đoạn đó. Tùy theo yêu cầu bài toán, giá trị này có thể là:
- Tổng các phần tử.
- Giá trị lớn nhất.
- Giá trị nhỏ nhất.
- GCD.
- XOR.
- Số lượng phần tử thỏa mãn điều kiện nào đó.
Nhờ việc lưu sẵn thông tin trung gian ở nhiều cấp độ khác nhau, cấu trúc dữ liệu này giúp tôi tránh được việc phải duyệt toàn bộ đoạn mỗi khi truy vấn xuất hiện.
Ý tưởng trực quan nhất giúp tôi hiểu Segment Tree
Điều khiến tôi hiểu Segment Tree nhanh nhất không phải là mã nguồn mà là cách hình dung trực quan.
Tôi tưởng tượng rằng node gốc đại diện cho toàn bộ mảng. Sau đó tôi liên tục chia đôi đoạn hiện tại thành hai nửa. Quá trình này lặp lại cho tới khi mỗi đoạn chỉ còn đúng một phần tử.
Ví dụ với mảng:
1 2 3 4
Nếu tôi lưu tổng trên mỗi đoạn thì cây sẽ có dạng:
10
/ \
3 7
/ \ / \
1 2 3 4
Nút gốc lưu tổng toàn bộ mảng:
1 + 2 + 3 + 4 = 10
Nút bên trái lưu:
1 + 2 = 3
Nút bên phải lưu:
3 + 4 = 7
Khi nhìn theo cách này, tôi nhận ra bản chất của Segment Tree rất đơn giản:
Mọi nút cha đều được xây dựng từ hai nút con.
Đây chính là ý tưởng quan trọng nhất của toàn bộ cấu trúc dữ liệu.
Vì sao truy vấn lại nhanh?
Đây là câu hỏi khiến tôi bối rối khá lâu.
Nếu một đoạn có hàng trăm nghìn phần tử, tại sao Segment Tree lại không cần duyệt hết tất cả các phần tử đó?
Câu trả lời nằm ở việc tái sử dụng các kết quả trung gian.
Giả sử tôi muốn tính tổng đoạn:
[2,5]
Thay vì đi qua từng phần tử trong đoạn này, Segment Tree sẽ tìm cách biểu diễn đoạn [2,5] thành tập hợp của một số đoạn con đã được lưu sẵn trong cây.
Ví dụ:
[2,2]
[3,3]
[4,5]
Mỗi đoạn nhỏ này đã có tổng được tính từ trước. Việc truy vấn chỉ còn là lấy các kết quả đó rồi cộng lại.
Điểm thú vị là số lượng đoạn cần sử dụng luôn tương đối nhỏ. Vì chiều cao cây chỉ khoảng log n, nên số node được thăm trong quá trình truy vấn cũng chỉ tỷ lệ với log n.
Đây chính là lý do Segment Tree có thể xử lý truy vấn rất nhanh ngay cả khi mảng có kích thước lớn.
Segment Tree khác gì so với mảng thông thường?
Khi mới học, tôi thấy việc nhớ công thức độ phức tạp không quá quan trọng bằng việc hiểu ý nghĩa của chúng.
Nếu chỉ dùng mảng thuần túy:
| Thao tác | Độ phức tạp |
|---|---|
| Update điểm | O(1) |
| Query đoạn | O(n) |
Nếu dùng Prefix Sum:
| Thao tác | Độ phức tạp |
|---|---|
| Query đoạn | O(1) |
| Update điểm | O(n) |
Còn với Segment Tree:
Còn với Segment Tree:
| Thao tác | Độ phức tạp |
|---|---|
| Query đoạn | O(log n) |
| Update điểm | O(log n) |
Segment Tree không cố làm cho một thao tác trở nên cực nhanh. Thay vào đó, nó tìm điểm cân bằng để cả cập nhật và truy vấn đều đạt hiệu năng tốt.
Trong thực tế, rất nhiều bài toán yêu cầu hàng trăm nghìn lần cập nhật và hàng trăm nghìn lần truy vấn. Khi đó, khả năng cân bằng này trở nên cực kỳ giá trị.
Khi nào tôi bắt đầu nghĩ đến Segment Tree?
Sau một thời gian luyện tập, tôi hình thành một phản xạ khá đơn giản.
Mỗi khi đọc đề bài và thấy đồng thời xuất hiện hai yếu tố:
- Truy vấn trên đoạn.
- Cập nhật dữ liệu.
tôi sẽ bắt đầu nghĩ tới Segment Tree.
Ví dụ:
- Cập nhật
a[i]. - Tìm tổng trên đoạn.
Hoặc:
- Cập nhật
a[i]. - Tìm giá trị lớn nhất trên đoạn.
Hoặc:
- Cập nhật
a[i]. - Tìm giá trị nhỏ nhất trên đoạn.
Hoặc:
- Cập nhật
a[i]. - Tính GCD trên đoạn.
Đó là những dấu hiệu rất quen thuộc.
Tất nhiên, không phải bài toán nào có truy vấn đoạn cũng cần Segment Tree. Đôi khi Fenwick Tree, Sparse Table hoặc các kỹ thuật khác sẽ phù hợp hơn. Tuy nhiên Segment Tree luôn là một trong những công cụ đầu tiên tôi cân nhắc.
Segment Tree và Fenwick Tree
Đây là câu hỏi mà tôi từng tự hỏi khá nhiều lần khi mới học.
Nhiều bài toán tổng đoạn có thể giải được bằng cả Fenwick Tree lẫn Segment Tree. Vậy nên chọn cái nào?
Khi tôi chọn Fenwick Tree
Tôi rất thích Fenwick Tree vì một số lý do:
- Mã nguồn ngắn.
- Dễ ghi nhớ.
- Tốc độ triển khai nhanh.
- Ít xảy ra lỗi.
Trong môi trường thi đấu, việc viết ít dòng hơn đôi khi cũng là một lợi thế.
Khi tôi chọn Segment Tree
Tôi thường chuyển sang Segment Tree khi bài toán không còn là tổng đơn thuần nữa.
Ví dụ:
- Maximum.
- Minimum.
- GCD.
- XOR.
- Kết hợp nhiều thông tin trong một node.
Segment Tree có tính tổng quát cao hơn rất nhiều. Sau khi quen với nó, tôi có cảm giác như đang sở hữu một bộ khung có thể tùy biến theo nhiều dạng bài khác nhau.
Độ phức tạp và bộ nhớ
Với Segment Tree cơ bản:
- Build:
O(n) - Query:
O(log n) - Update:
O(log n)
Điều khiến tôi bất ngờ khi mới học là thao tác xây dựng cây lại chỉ mất O(n) thay vì O(n log n).
Nguyên nhân là mỗi phần tử chỉ đóng góp vào một số lượng hữu hạn các phép tính trong quá trình xây dựng cây. Tổng số node trong cây cũng chỉ tỷ lệ với O(n).
Về bộ nhớ, cách khai báo phổ biến nhất là:
tree[4 * n]
Tôi đã từng thắc mắc rất nhiều về con số 4 này. Thực chất đây chỉ là một cách đơn giản để đảm bảo luôn đủ không gian cho toàn bộ cây mà không cần tính toán quá chi tiết số node thực tế.
Cài đặt Segment Tree cơ bản
Để minh họa, tôi sẽ sử dụng phiên bản quen thuộc nhất: Point Update + Range Sum Query.
Khai báo
const int MAXN = 200000;
int64_t tree[4 * MAXN];
Build
void build(int node, int l, int r, vector<int>& a) {
if (l == r) {
tree[node] = a[l];
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid, a);
build(node << 1 | 1, mid + 1, r, a);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
Điều quan trọng nhất trong hàm build là quy tắc gộp dữ liệu. Sau khi xây dựng xong hai nhánh con, giá trị của node cha được tính từ hai node con.
Nếu thay phép cộng bằng max, min hoặc gcd, tôi hoàn toàn có thể biến cấu trúc này thành một loại Segment Tree khác.
Query
int64_t query(int node, int l, int r, int ql, int qr) {
if (r < ql || qr < l)
return 0;
if (ql <= l && r <= qr)
return tree[node];
int mid = (l + r) >> 1;
return (query(node << 1, l, mid, ql, qr) +
query(node << 1 | 1, mid + 1, r, ql, qr));
}
Khi đọc hàm này lần đầu, tôi cảm thấy nó khá khó hiểu. Tuy nhiên sau khi vẽ cây ra giấy và mô phỏng vài truy vấn bằng tay, tôi nhận ra hàm query thực chất chỉ xử lý ba trường hợp:
- Không giao nhau.
- Nằm hoàn toàn bên trong đoạn truy vấn.
- Giao nhau một phần.
Nắm được ba trường hợp này thì việc hiểu hàm query trở nên dễ dàng hơn rất nhiều.
Update
void update(int node, int l, int r, int pos, int value) {
if (l == r) {
tree[node] = value;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(node << 1, l, mid, pos, value);
else
update(node << 1 | 1, mid + 1, r, pos, value);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
Một vài bài toán kinh điển
Range Sum Query
Đây gần như là bài toán nhập môn của Segment Tree.
Mục tiêu là hỗ trợ đồng thời:
- Cập nhật một phần tử.
- Tính tổng trên đoạn.
Đây là ví dụ đơn giản nhất để hiểu vì sao Segment Tree tồn tại.
Range Maximum Query
Điều khiến tôi bất ngờ nhất khi học Segment Tree là việc chuyển từ Sum sang Max dễ hơn tôi tưởng rất nhiều.
Thay vì lưu tổng:
sum
tôi lưu:
max
và thay đổi phép gộp:
tree[node] = max(tree[left], tree[right]);
Phần còn lại gần như giữ nguyên.
Khoảnh khắc nhận ra điều này giúp tôi hiểu rằng bản chất của Segment Tree không nằm ở phép tính cụ thể nào. Điều quan trọng là cơ chế chia đoạn và gộp kết quả.
Dynamic Range Minimum Query (CSES)
Đây là một trong những bài đầu tiên giúp tôi cảm thấy thực sự tự tin khi sử dụng Segment Tree.
Bài toán yêu cầu:
- Cập nhật phần tử.
- Tìm giá trị nhỏ nhất trên đoạn.
Sau khi giải xong bài này và một vài bài tương tự, tôi bắt đầu nhận ra rằng Sum Tree, Max Tree và Min Tree thực chất chỉ là những biến thể khác nhau của cùng một ý tưởng nền tảng.
Những lỗi tôi từng gặp khi học Segment Tree
Khai báo sai kích thước cây
Đây gần như là lỗi nhập môn.
Ban đầu tôi từng khai báo:
tree[n];
và nhanh chóng nhận Runtime Error.
Sau đó tôi mới biết rằng hầu hết mọi người đều sử dụng:
tree[4 * n];
để tránh những rắc rối liên quan đến kích thước cây.
Quên cập nhật node cha
Tôi đã nhiều lần sửa đúng giá trị của node lá nhưng quên cập nhật lại toàn bộ các node tổ tiên phía trên.
Kết quả là:
- Update có vẻ đúng.
- Chương trình không bị lỗi.
- Nhưng query cho kết quả sai.
Đây là dạng bug rất khó thấy nếu chỉ nhìn vào một vài test đơn giản.
Sai điều kiện giao nhau
Một lỗi khác mà tôi gặp đi gặp lại là viết sai phần kiểm tra giao nhau:
if (r < ql || qr < l)
Chỉ cần đổi nhầm một dấu < thành <=, chương trình có thể sai ở một vài trường hợp biên rất hiếm gặp.
Những lỗi như vậy đôi khi khiến tôi mất nhiều thời gian hơn cả việc nghĩ ra thuật toán.
Nhầm lẫn giữa chỉ số 0-based và 1-based
Đây có lẽ là lỗi xuất hiện nhiều nhất trong các kỳ thi lập trình của tôi.
Đề bài sử dụng chỉ số bắt đầu từ 1 nhưng tôi lại xây dựng cây dựa trên mảng bắt đầu từ 0, hoặc ngược lại.
Kết quả là toàn bộ truy vấn bị lệch một đơn vị và cho ra đáp án hoàn toàn sai.
Từ đó về sau, mỗi khi bắt đầu viết Segment Tree, tôi luôn tự hỏi trước: “Mình đang dùng hệ chỉ số nào?”
Điều tôi rút ra sau khi học Segment Tree
Khi nhìn lại quá trình học competitive programming của bản thân, tôi nhận ra rằng rào cản lớn nhất của Segment Tree không phải là cú pháp hay đệ quy.
Điều khó nhất nằm ở cách tư duy.
Khi mới học lập trình, chúng ta quen nhìn dữ liệu dưới dạng từng phần tử riêng lẻ. Segment Tree buộc chúng ta phải thay đổi góc nhìn đó. Thay vì tập trung vào từng giá trị cụ thể, chúng ta bắt đầu suy nghĩ về các đoạn và cách kết hợp thông tin giữa các đoạn với nhau.
Một khi đã quen với tư duy này, Segment Tree bỗng trở nên rất tự nhiên. Thậm chí nhiều cấu trúc dữ liệu nâng cao về sau cũng trở nên dễ tiếp cận hơn rất nhiều.
Tôi từng nghĩ Segment Tree là một trong những chủ đề khó nhất của competitive programming. Nhưng sau khi hiểu được bản chất của nó, tôi nhận ra rằng đây thực ra chỉ là một cây nhị phân lưu trữ thông tin tổng hợp trên các đoạn của mảng. Ý tưởng cốt lõi không hề phức tạp như vẻ ngoài của những đoạn mã dài và đầy toán tử bit.
Kết luận
Nhìn lại hành trình học thuật toán của mình, Segment Tree là một trong những cấu trúc dữ liệu mang lại cho tôi cảm giác “vỡ ra” rõ rệt nhất. Trong một thời gian dài, tôi luôn xem nó là thứ gì đó rất đáng sợ. Tôi nhìn thấy đệ quy, cây nhị phân, các đoạn [l, r] lồng vào nhau và vô số toán tử dịch bit khó nhớ. Mỗi lần mở một đoạn mã Segment Tree ra đọc, tôi đều có cảm giác mình chưa sẵn sàng để hiểu nó.
Thế nhưng khi kiên nhẫn đi từng bước một, bắt đầu từ bài toán tổng đoạn đơn giản nhất, mọi thứ dần trở nên sáng tỏ. Tôi nhận ra rằng Segment Tree không phải là một tập hợp những mẹo kỹ thuật khó nhớ. Nó chỉ là một cách tổ chức dữ liệu thông minh nhằm lưu lại các kết quả trung gian để phục vụ truy vấn và cập nhật hiệu quả hơn.
Điều thú vị là Segment Tree thường không phải đích đến cuối cùng. Sau khi hiểu Segment Tree cơ bản, rất nhiều chủ đề nâng cao như Lazy Propagation, Persistent Segment Tree hay Segment Tree Beats cũng trở nên gần gũi hơn. Những khái niệm tưởng như rất khó trước đây thực chất đều được xây dựng trên cùng một nền tảng.
Nếu bạn đang học competitive programming và đã quen với mảng, Prefix Sum hoặc Fenwick Tree, tôi nghĩ Segment Tree là bước tiếp theo rất đáng để đầu tư thời gian. Những ngày đầu có thể hơi vất vả vì phải thay đổi cách nhìn dữ liệu, nhưng khi vượt qua được giai đoạn đó, bạn sẽ có trong tay một công cụ cực kỳ mạnh mẽ và xuất hiện trong vô số bài toán thực tế.
Và biết đâu, giống như tôi nhiều năm trước, thứ mà bạn từng trì hoãn học lâu nhất lại trở thành một trong những cấu trúc dữ liệu hữu ích nhất trên hành trình chinh phục thuật toán của mình.
