¶ Cây Phân Đoạn (cơ bản)
Nguồn: wcipeg, cp-algorithms, Tất tần tật về Cây Phân Đoạn (Segment Tree) - VNOI
Tác giả:
- Nguyễn Châu Khanh - VNU University of Engineering and Technology (VNU-UET)
Reviewer:
- Trần Xuân Bách - HUS High School for Gifted Students
- Nguyễn Nhật Minh Khôi - VNUHCM-University of Science
- Nguyễn Phú Bình - Hung Vuong High School for the Gifted, Binh Duong Province
- Ngô Nhật Quang - HUS High School for Gifted Students
- Hồ Ngọc Vĩnh Phát - VNUHCM-University of Science
LƯU Ý: Mọi số thứ tự trong bài viết đều được đánh số bắt đầu từ .
¶ Mở đầu
Cây phân đoạn (Segment Tree) là một cấu trúc dữ liệu rất linh hoạt được sử dụng nhiều trong các kỳ thi, đặc biệt là trong những bài toán xử lý trên dãy số.
Ở bài viết này, ta sẽ chỉ tìm hiểu về những kiến thức cơ bản của Segment Tree và một số bài tập thường gặp trong các kì thi.
Còn nếu bạn muốn tìm hiểu sâu hơn về Segment Tree thì bạn có thể tham khảo bài viết: Tất tần tật về Cây Phân Đoạn (Segment Tree) - VNOI.
¶ Ý tưởng
Một trong những ứng dụng phổ biến nhất của Segment Tree là giải quyết bài toán . Trong bài toán này, ta được cho một mảng và truy vấn; mỗi truy vấn gồm cặp số và , yêu cầu tìm phần tử có giá trị nhỏ nhất trong đoạn từ đến của mảng .
- Ví dụ: Ta có mảng . Với truy vấn và , đáp án sẽ là . Sau đó, một truy vấn khác với và thì đáp án là ; v.v...
Có nhiều giải pháp khác nhau để giải quyết bài toán này nhưng Segment Tree thường là lựa chọn thích hợp nhất, đặc biệt là khi có thêm hoạt động sửa đổi được xen kẽ với các truy vấn.
Giải pháp chia để trị
-
Ta có giải pháp chia để trị sau:
-
Nếu dãy đang xét chứa một phần tử, thì bản thân phần tử đó là giá trị nhỏ nhất trong dãy đó.
-
Nếu không, ta chia dãy đó thành hai dãy con liên tiếp nhỏ hơn, mỗi dãy con gần bằng một nửa kích thước của dãy ban đầu, và tìm giá trị nhỏ nhất tương ứng của chúng. Giá trị nhỏ nhất của dãy ban đầu chính là giá trị nhỏ hơn giữa hai giá trị nhỏ nhất của các dãy con.
- Ví dụ mô tả thuật toán chia để trị với mảng :
-
-
Nhận thấy rằng, khi ta sửa đổi giá trị của một phần tử bất kỳ trong mảng thì số lượng đoạn cần tính lại không nhiều. Vậy nên ta sẽ lưu lại kết quả và chỉ tính lại khi thực sự cần thiết.
- Ví dụ: Trong ví dụ bên trên, khi sửa đổi phần tử có giá trị thành giá trị thì ta chỉ cần tính lại giá trị nhỏ nhất của các đoạn , , và .
Tổng quát
-
Gọi là giá trị của phần tử thứ trong mảng, việc tìm giá trị nhỏ nhất có thể được viết dưới dạng hàm đệ quy như sau:
- Với là phần tử có giá trị nhỏ nhất trong đoạn từ đến của mảng .
-
Do đó, khi ta sửa đổi giá trị của phần tử thứ trong mảng thì ta chỉ cần tính lại kết quả của các hàm với .
Giả sử rằng ta sử dụng hàm được định nghĩa ở trên để xác định , với là số lượng phần tử của mảng. Khi lớn, hàm gọi đệ quy này sẽ có hai "con", một trong số đó là lệnh gọi đệ quy và lệnh còn lại là . Mỗi hàm này sau đó sẽ lại có thêm hai "con" của riêng nó, và cứ tiếp tục như vậy cho đến khi đạt được trường hợp cơ sở (khi ).
Nếu ta biểu diễn các hàm gọi đệ quy này bằng cấu trúc cây, thì hàm sẽ là gốc, nó sẽ có hai con, mỗi con sẽ có thêm hai con nữa, v.v...; các trường hợp cơ sở sẽ là lá của cây. Khi đó, cấu trúc cây gọi đệ quy của hàm chính là cấu trúc của cây phân đoạn. Và việc sửa đổi giá trị phần tử trong mảng cũng chính là bản chất của thao tác cập nhật trên cây phân đoạn (sẽ được mô tả rõ hơn ở phần sau).
- Ví dụ: Ta có mảng được kiểm soát bởi cây phân đoạn sau:
¶ Cấu trúc
Bây giờ ta đã sẵn sàng để xác định cấu trúc của cây phân đoạn:
- Segment Tree là một cây. Cụ thể hơn, nó là một cây nhị phân đầy đủ (mỗi nút là lá hoặc có đúng nút con).
- Mỗi nút quản lý một dãy các đối tượng liên tiếp, trong nút chứa thông tin tổng hợp từ các đối tượng mà nó quản lý.
- Với một dãy số gồm phần tử, nút gốc quản lý các đối tượng từ tới .
- Nếu một nút quản lý dãy các đối tượng từ tới thì nút con trái của nó quản lý các đối tượng từ tới và nút con phải của nó quản lý các đối tượng từ tới Với .
- Nếu một nút chỉ quản lý một đối tượng thì nó sẽ là nút lá và không có nút con.
- Chiều cao của cây phân đoạn là , bởi vì khi đi xuống từ gốc đến lá, kích thước của mỗi đoạn giảm đi một nửa.
- Tại mỗi độ sâu của cây, không có phần tử nào được quản lý bởi nút khác nhau của cây.
¶ Các thao tác trên cây phân đoạn
Có thao tác cơ bản trên cây phân đoạn:
¶ Xây dựng
Để có thể có thể lấy giá trị và sửa đổi dãy số, trước tiên ta cần phải xây dựng một cây phân đoạn hợp lệ.
Trước khi xây dựng cây phân đoạn, ta cần quyết định:
- Thông tin được lưu trữ tại mỗi nút của cây phân đoạn. Ví dụ: Trong cây phân đoạn lấy giá trị nhỏ nhất, một nút sẽ lưu trữ giá trị nhỏ nhất của các phần tử trong đoạn mà nó quản lý.
- Phép toán hợp nhất hai nút con trong một cây phân đoạn. Ví dụ: Trong cây phân đoạn lấy giá trị nhỏ nhất, hai nút con tương ứng với đoạn và đoạn sẽ được hợp nhất thành một nút tương ứng với đoạn bằng cách lấy min các giá trị của hai nút con.
Lưu ý rằng một đỉnh là "đỉnh lá", nếu đoạn tương ứng của nó chỉ bao gồm một giá trị trong mảng ban đầu. Nó là đỉnh thấp nhất của cây phân đoạn. Giá trị của nó sẽ bằng phần tử tương ứng.
Có cách để xây dựng một cây phân đoạn:
-
Cách 1: Xây dựng "từ dưới lên trên"
- Để xây dựng cây phân đoạn, ta sẽ bắt đầu ở các nút có độ sâu thấp nhất (các nút lá) và gán cho chúng các giá trị tương ứng. Rồi từ đó, ta có thể tính toán lên các nút cha bằng cách "hợp nhất" lần lượt nút con và lặp lại quy trình cho đến khi đạt đến đỉnh gốc.
-
Cách 2: Xây dựng "từ trên xuống dưới"
- Cấu trúc từ trên xuống là sử dụng đệ quy. Tức là ta sẽ bắt đầu từ đỉnh gốc đến các đỉnh lá bằng mô hình đệ quy như sau:
- Nếu nút đang xét là nút lá, ta có thể lấy được ngay giá trị tương ứng từ mảng.
- Ngược lại, nếu nút đang xét không phải là nút lá, ta gọi đệ quy để tính toán giá trị của hai nút con. Sau khi hai lệnh gọi đệ quy được thực hiện, giá trị của nút đang xét sẽ bằng giá trị được "hợp nhất" từ hai nút con.
- Do thủ tục đệ quy bắt đầu từ đỉnh gốc nên ta có thể tính toán được toàn bộ cây phân đoạn.
- Cấu trúc từ trên xuống là sử dụng đệ quy. Tức là ta sẽ bắt đầu từ đỉnh gốc đến các đỉnh lá bằng mô hình đệ quy như sau:
¶ Cập nhật
Bây giờ ta muốn sửa đổi một phần tử cụ thể trong mảng, giả sử ta muốn thực hiện việc gán . Và phải cập nhật lại cây phân đoạn, sao cho nó tương ứng với mảng mới đã sửa đổi.
Để làm như vậy, trước tiên ta cần sửa đổi nút lá tương ứng. Các nút lá khác không bị ảnh hưởng, vì mỗi nút lá chỉ được liên kết với một phần tử trong mảng. Nút cha của nút đã sửa đổi cũng bị ảnh hưởng, vì đoạn nó quản lý cũng chứa phần tử đã sửa đổi, và các nút tổ tiên của nó cũng vậy, v.v... cho đến nút gốc.
Nói cách khác, tất cả các nút nằm trên đường đi đơn từ gốc đến nút lá tương ứng đều bị ảnh hưởng. Ngoài ra, không còn nút nào khác bị ảnh hưởng. Do đó, với một dãy số gồm phần tử thì chiều cao của cây phân đoạn tương ứng sẽ là nên chỉ có nút cần được cập nhật.
- Ví dụ: Cho mảng . Phần tử có giá trị được thay đổi thành giá trị trong cây phân đoạn lấy giá trị nhỏ nhất.
Thao tác cập nhật cây phân đoạn có thể được thực hiện bằng cách sử dụng một hàm đệ quy:
- Để thực hiện cập nhật từ trên xuống, ta bắt đầu từ nút gốc; điều này dẫn đến lệnh gọi đệ quy tới một nút con quản lí đoạn chứa phần tử cần sửa đổi (nút con còn lại và cây con của nó không bị ảnh hưởng); v.v... Cho đến trường hợp cơ sở là nút lá được liên kết với phần tử cần cập nhật, ta sửa lại giá trị của nút lá đó.
- Sau khi hoàn tất lệnh gọi đệ quy cho các nút con (trừ trường hợp cơ sở), giá trị của nút đang xét sẽ được cập nhật lại theo giá trị hai nút con của nó.
Tương tự như thao tác xây dựng cây phân đoạn, cách cập nhật cây phân đoạn "từ dưới lên" cũng có thể thực hiện được.
¶ Lấy giá trị
Bây giờ, ta cần phải trả lời các truy vấn lấy giá trị. Ví dụ như: cho hai số nguyên và , hãy xác định phần tử có giá trị nhỏ nhất trong đoạn của mảng với khoảng thời gian là .
Do thao tác lấy giá trị này phức tạp hơn thao tác cập nhật cây phân đoạn nên ta sẽ lấy một ví dụ minh họa để dễ hình dung:
- Giả sử, cho mảng và ta muốn biết phần tử nhỏ nhất trong đoạn của mảng .
- Gọi là phần tử có giá trị nhỏ nhất trong đoạn . Ta thấy rằng mỗi nút trong cây phân đoạn đều quản lí một đoạn nào đó, ví dụ như nút gốc chứa , nút con bên trái là , nút bên phải là , v.v...; và mỗi nút lá chứa . Nhưng không có nút nào chứa ; tuy nhiên, ta nhận thấy rằng , và có tồn tại các nút trong cây phân đoạn chứa hai giá trị đó (được hiển thị bằng màu xanh dương trong hình trên).
Dễ thấy rằng với . Do đó, ta phải xác định tập hợp ít nút nhất sao cho tổng tất cả các phạm vi mà các nút đó quản lí đúng bằng đoạn cần truy vấn. Sự kết hợp của tập hợp các nút đó chính xác là đáp án mà ta tìm kiếm.
Để làm như vậy, ta sẽ bắt đầu từ gốc và đệ quy qua các nút mà phạm vi quản lí của nó có ít nhất một phần tử chung với đoạn cần truy vấn.
Trong ví dụ trên với , xét hai nút con của gốc, ta nhận thấy rằng cả nút con bên trái và bên phải đều quản lí một số các phần tử con thuộc đoạn cần truy vấn (đoạn ). Do đó, ta sẽ thực hiện lệnh gọi đệ quy trên cả hai nút con của nút gốc. Khi đó, nút con bên trái của gốc đóng vai trò như một trường hợp cơ sở, vì phạm vi quản lí của nó được chứa hoàn toàn bên trong đoạn truy vấn; vậy nên nó được chọn (đánh dấu bằng màu xanh dương).
Còn với nút con bên phải của gốc (nút chứa ); ta nhận thấy rằng nút con bên trái của nút , tức là có quản lí một số các phần tử con thuộc đoạn cần truy vấn, nhưng nút con bên phải là thì không. Vì vậy, ta chỉ tiếp tục gọi đệ quy trên nút con bên trái là nút chứa và bỏ qua không gọi đệ quy nút con bên phải là nút chứa .
Khi đấy, nút con bên trái đó (nút ) sẽ là một trường hợp cơ sở khác, nó cũng được chọn (và đánh dấu bằng màu xanh dương).
Đệ quy kết thúc và giá trị nhỏ nhất của đoạn cần truy vấn chính là giá trị nhỏ nhất của các nút đã được chọn.
¶ Cài đặt
Thứ khiến ta cần phải cân nhắc ở đây chính là cách lưu trữ cây phân đoạn. Tất nhiên, ta có thể tạo ra một cấu trúc cây và danh sách cạnh, lưu trữ phạm vi quản lí của từng nút và các thông tin của nó. Tuy nhiên điều này đòi hỏi phải lưu trữ nhiều thông tin dư thừa.
Thay vào đó, ta sẽ sử dụng một thủ thuật đơn giản để làm cho việc này trở nên hiệu quả hơn rất nhiều. Ta sẽ chỉ lưu trữ các thông tin của từng nút vào trong một mảng. Thông tin của nút gốc lưu ở chỉ số , thông tin của hai nút con của nó lưu ở chỉ số và , thông tin của các nút con của hai nút đó sẽ lưu ở chỉ số từ đến , v.v... Dễ dàng nhận thấy, con bên trái của nút có chỉ số được lưu trữ tại chỉ số và con bên phải được lưu trữ tại chỉ số .
-
Ví dụ minh họa: Cho mảng , ta có (với là mảng biểu diễn cho Segment Tree, lưu lại thông tin của mỗi nút).
- Chỉ số trên mảng được viết bằng màu đỏ bên cạnh mỗi nút, ví dụ như nút có chỉ số sẽ quản lí đoạn và nút con bên trái của nó có chỉ số , còn nút con bên phải có chỉ số .
Điều này đơn giản hóa việc cài đặt rất nhiều. Ta không cần lưu hết toàn bộ cấu trúc của cây trong bộ nhớ. Mà nó sẽ được định nghĩa một cách ngầm định. Ta chỉ cần một mảng chứa thông tin của tất cả các phân đoạn.
Để dễ hình dung, ta lấy ví dụ cụ thể:
- Cho dãy gồm phần tử với .
- Có truy vấn . Mỗi truy vấn thuộc trong loại:
- Loại 1: Có dạng : Gán giá trị cho phần tử ở vị trí .
- Loại 2: Có dạng : Tìm phần tử có giá trị nhỏ nhất trong đoạn .
Cách đơn giản nhất là dùng một mảng duy trì giá trị các phần tử. Với truy vấn thì ta gán . Với truy vấn thì ta dùng một vòng lặp từ đến để tìm giá trị nhỏ nhất. Rõ ràng cách này có độ phức tạp là và không thể chạy trong thời gian cho phép.
Do đó, ta sẽ cài đặt Segment Tree để giải quyết bài toán trên như sau:
Cấu trúc dữ liệu:
- Hằng số
maxN = 100007. - Hằng số
inf = 1000000007. - Mảng
st[]- Lưu thông tin của mỗi nút trên Segment Tree.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 1e5 + 7;
int n, q;
int a[maxN];
int st[4 * maxN]; // Lí do sử dụng kích thước mảng là 4 * maxN sẽ được giải thích ở phần sau
// Thủ tục xây dựng cây phân đoạn
void build(int id, int l, int r) {
// Đoạn chỉ gồm 1 phần tử, không có nút con
if (l == r) {
st[id] = a[l];
return;
}
// Gọi đệ quy để xử lý các nút con của nút id
int mid = l + r >> 1; // (l + r) / 2
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
// Cập nhật lại giá trị min của đoạn [l, r] theo 2 nút con
st[id] = min(st[2 * id], st[2 * id + 1]);
}
// Thủ tục cập nhật
void update(int id, int l, int r, int i, int val) {
// i nằm ngoài đoạn [l, r], ta bỏ qua nút id
if (l > i || r < i) return;
// Đoạn chỉ gồm 1 phần tử, không có nút con
if (l == r) {
st[id] = val;
return;
}
// Gọi đệ quy để xử lý các nút con của nút id
int mid = l + r >> 1; // (l + r) / 2
update(2 * id, l, mid, i, val);
update(2 * id + 1, mid + 1, r, i, val);
// Cập nhật lại giá trị min của đoạn [l, r] theo 2 nút con
st[id] = min(st[2 * id], st[2 * id + 1]);
}
// Hàm lấy giá trị
int get(int id, int l, int r, int u, int v) {
// Đoạn [u, v] không giao với đoạn [l, r], ta bỏ qua đoạn này
if (l > v || r < u) return inf;
/* Đoạn [l, r] nằm hoàn toàn trong đoạn [u, v] mà ta đang truy vấn,
ta trả lại thông tin lưu ở nút id */
if (l >= u && r <= v) return st[id];
// Gọi đệ quy với các nút con của nút id
int mid = l + r >> 1; // (l + r) / 2
int get1 = get(2 * id, l, mid, u, v);
int get2 = get(2 * id + 1, mid + 1, r, u, v);
// Trả ra giá trị nhỏ nhất theo 2 nút con
return min(get1, get2);
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
cin >> q;
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) update(1, 1, n, x, y); // Gán giá trị y cho phần tử ở vị trí x
else cout << get(1, 1, n, x, y) << '\n'; // In ra giá trị nhỏ nhất trong đoạn [x, y]
}
}
¶ Đánh giá
Ở phần Các thao tác trên cây phân đoạn có nhắc đến cách để cài đặt Segment Tree. Vì sự khác biệt về tốc độ của hai cách có thể là không đáng kể, nên bài viết này sẽ chỉ cài đặt theo cách thông thường nhất là sử dụng phương pháp đệ quy.
Segment Tree còn có một cách cài đặt khác sử dụng ít bộ nhớ hơn (sử dụng tối đa phần tử), cài đặt ngắn hơn và chạy nhanh hơn. Tuy nhiên thì nó không dễ hiểu bằng cách cài đặt trên. Bạn có thể tham khảo thêm tại đây: VNOI - Efficient and easy segment trees.
¶ Phân tích độ phức tạp
¶ Bộ nhớ
Ta xét trường hợp:
- TH1: : Cây phân đoạn đầy đủ, ở độ sâu cuối cùng có đúng lá, và các độ sâu thấp hơn không có nút lá nào (và các nút này đều có đúng con). Như vậy:
- Tầng : có nút
- Tầng : có nút
- ...
Tổng số nút không quá (vì tổng số nút theo công thức cấp số nhân).
- TH2: Với và : Số nút của cây phân đoạn không quá số nút của cây phân đoạn với .
Do đó, số nút của cây cho dãy phần tử (với ) là không quá , giá trị này xấp xỉ . Bằng thực nghiệm, ta thấy dùng là đủ.
Tham khảo thêm các cách chứng minh khác tại đây: Codeforces – Blog entry 49939.
¶ Thời gian
¶ Thao tác xây dựng
Thao tác xây dựng sẽ yêu cầu một số lượng hoạt động không đổi trên mỗi nút của cây phân đoạn. Với mảng có phần tử thì số lượng nút của cây phân đoạn xấp xỉ (đã chứng minh ở trên), và vì thao tác xây dựng mất thời gian tuyến tính nên sẽ có độ phức tạp là .
Ta có thể nhận thấy rằng thao tác xây dựng nhanh hơn so với việc thực hiện các thao tác cập nhật riêng biệt (việc duyệt từng phần tử của mảng để cập nhật sẽ mất độ phức tạp ).
¶ Thao tác cập nhật
Với thao tác cập nhật, một số lượng các hoạt động không đổi được thực hiện cho mỗi nút trên đường đi đơn từ gốc đến nút lá tương ứng với phần tử cần sửa đổi. Đồng nghĩa với việc ở mỗi độ sâu của cây, ta chỉ gọi đệ quy tới không quá nút con.
Phân tích đoạn code trên, ta xét các trường hợp:
- Phần tử cần xét không nằm trong đoạn do nút quản lý. Trường hợp này ta dừng lại, không xét tiếp.
- Phần tử cần xét nằm trong đoạn do nút quản lý. Ta xét các con của nút . Tuy nhiên chỉ có con của nút chứa phần tử cần xét và ta sẽ phải xét tiếp các con của nút này. Với nút con còn lại, ta sẽ dừng ngay mà không xét các con của nó nữa.
Vì số lượng các nút trên đường đi đơn từ gốc đến nút lá tương ứng được giới hạn bởi chiều cao của cây là nên độ phức tạp của thao tác cập nhật sẽ là .
¶ Thao tác lấy giá trị
Trước tiên, ta hãy xem xét từng độ sâu của của cây. Từ đó có thể thấy rằng đối với mỗi độ sâu, ta chỉ truy cập không quá nút. Và vì chiều cao của cây là nên độ phức tạp của thao tác lấy giá trị là .
Ta có thể chứng minh rằng mệnh đề này (truy cập nhiều nhất bốn nút trong mỗi độ sâu) là đúng bằng phương pháp quy nạp:
-
Ở độ sâu đầu tiên, ta chỉ truy cập duy nhất một nút là nút gốc, vì vậy ở đây ta truy cập ít hơn nút.
-
Bây giờ, ta hãy xem xét một độ sâu bất kì. Theo giả thuyết quy nạp là ta thăm nhiều nhất nút. Nếu ta chỉ thăm nhiều nhất nút, thì ở độ sâu tiếp theo, số lượng nút được thăm nhiều nhất sẽ là nút. Điều đó thật hiển nhiên, bởi vì mỗi nút có thể tạo ra nhiều nhất lệnh gọi đệ quy.
-
Vì vậy, giả sử rằng ta truy cập hoặc nút trong độ sâu hiện tại. Từ các nút đó, ta sẽ phân tích kỹ hơn các nút nằm ở giữa (nghĩa là nút thứ hai từ trái sang với số lượng nút đang được truy cập là và nút thứ với số nút đang được truy cập là ) . Vì truy vấn yêu cầu lấy giá trị của một đoạn con liên tục, ta biết rằng các phân đoạn tương ứng với các nút đã thăm ở giữa sẽ được bao phủ hoàn toàn bởi phân đoạn của truy vấn. Do đó các nút này sẽ không thực hiện bất kỳ lệnh gọi đệ quy nào tới các nút con nữa. Vì vậy, chỉ nút bên trái nhất và nút bên phải nhất mới có khả năng tiếp tục gọi đệ quy. Và hai nút đó sẽ chỉ tạo ra nhiều nhất lệnh gọi đệ quy, vì vậy độ sâu tiếp theo cũng sẽ đáp ứng đúng mệnh đề.
- Ví dụ: Giả sử, đoạn cần truy vấn là đoạn . Ở độ sâu thứ , ta sẽ truy cập vào ba nút quản lí các đoạn , và (được đánh dấu bằng màu xanh dương). Khi đó, vì nút quản lí đoạn nằm hoàn toàn bên trong đoạn nên hàm đệ quy sẽ trả ra luôn giá trị của nút đó, mà không gọi đệ quy tới các nút con. Chỉ có hai nút là nút bên trái nhất quản lí đoạn và nút bên phải nhất quản lí đoạn mới được tiếp tục gọi đệ quy.
-
Ta cũng có thể nói rằng một nhánh cây phân đoạn sẽ tiếp cận dần tới giới hạn bên trái của truy vấn và nhánh thứ hai tiếp cận tới giới hạn bên phải.
Do đó, ta sẽ chỉ truy cập nhiều nhất nút trên cây phân đoạn, và đó cũng chính là độ phức tạp của thao tác lấy giá trị.
¶ Ví dụ 1
¶ Bài toán
Bạn được cho một mảng gồm số nguyên. Ban đầu tất cả các số của mảng đều là . Nhiệm vụ của bạn là xử lí loại truy vấn:
- Loại có dạng : Gán phần tử ở vị trí thứ trong dãy thành số .
- Loại có dạng : In ra tổng các phần tử trong đoạn từ đến .
Với mỗi truy vấn loại , hãy in ra câu trả lời trên một dòng.
(với là số lượng truy vấn).
¶ Phân tích
Vì ban đầu giá trị của tất cả phần tử trong mảng đều bằng nên ta không cần phải thực hiện thao tác xây dựng cây phân đoạn.
Nhận thấy rằng, trên cây phân đoạn, mỗi nút không phải lá sẽ chứa tổng giá trị tại các nút con của nó. Do đó, ta chỉ cần thay thế tất cả các phép toán min ở ví dụ trên (trong phần Cài đặt) bằng các phép toán cộng.
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
maxN = 100007. - Mảng
st[]- Lưu thông tin của mỗi nút trên Segment Tree.
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 7;
int n, q;
int a[maxN];
long long st[4 * maxN];
// Thủ tục cập nhật
void update(int id, int l, int r, int i, int val) {
if (l > i || r < i) return;
if (l == r) {
st[id] = val;
return;
}
int mid = l + r >> 1;
update(2 * id, l, mid, i, val);
update(2 * id + 1, mid + 1, r, i, val);
st[id] = st[2 * id] + st[2 * id + 1];
}
// Hàm lấy tổng giá trị
long long get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
long long get1 = get(2 * id, l, mid, u, v);
long long get2 = get(2 * id + 1, mid + 1, r, u, v);
return get1 + get2;
}
int main() {
cin >> n >> q;
while (q--){
int type, x, y;
cin >> type >> x >> y;
if (type == 1) update(1, 1, n, x, y);
else cout << get(1, 1, n, x, y) << '\n';
}
}
¶ Đánh giá
Độ phức tạp
Với mỗi truy vấn, ta sẽ mất cho mỗi thao tác trên Segment Tree. Do đó, độ phức tạp của thuật toán là .
¶ Ví dụ 2
¶ Bài toán
Cho dãy số .
Hàm = , với .
Cho câu hỏi dạng , hãy tính các .
¶ Phân tích
Ở bài toán này, mỗi nút của cây phân đoạn lưu lại các thông tin sau:
pre: Tiền tố có tổng giá trị lớn nhất trên đoạn.suf: Hậu tố có tổng giá trị lớn nhất trên đoạn.sum: Tổng giá trị các phần tử trên đoạn.maxsum: Tổng giá trị lớn nhất của đoạn con nằm trong đoạn mà nút đó quản lí.
Bây giờ, ta cần phải xác định các phép toán để "hợp nhất" hai nút con:
-
pre: Dễ thấy rằng tiền tố lớn nhất của nút cha sẽ bằng max tiền tố của nút con bên trái và tổng giá trị của nút con bên trái cộng với tiền tố của nút con bên phải.- Minh họa: với .
-
suf: Hậu tố lớn nhất của nút cha sẽ bằng max hậu tố của nút con bên phải và tổng giá trị của nút con bên phải cộng với hậu tố của nút con bên trái. Cách tính hậu tố tương tự như với tiền tố nên sẽ không minh họa lại nữa. -
sum: Ta có thể dễ dàng tính toán giống như ở Ví dụ 1 bằng cách lấy tổng giá trị nút con. -
maxsum:-
Xét trường hợp:
- TH1: Đoạn con có tổng lớn nhất nằm hoàn toàn bên trong nút con bên trái.
- TH2: Đoạn con có tổng lớn nhất nằm hoàn toàn bên trong nút con bên phải.
- TH3: Một phần của đoạn con có tổng lớn nhất nằm ở nút con bên phải, và phần còn lại nằm ở nút con bên trái.
-
Ở trường hợp đầu tiên thì ta chỉ cần trực tiếp lấy giá trị của đoạn con lớn nhất từ các nút con.
-
Ở trường hợp thứ , giá trị của đoạn con lớn nhất sẽ là tổng hậu tố lớn nhất của nút con bên trái với tiền tố lớn nhất của nút con bên phải.
- Minh họa: Trường hợp , với :
-
Khi đó, giá trị của đoạn con lớn nhất nằm trong đoạn được quản lí bởi nút cha sẽ là giá trị lớn nhất của cả ba trường hợp trên.
-
Với mỗi truy vấn, đáp án chính là .
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
inf = 1000000007. - Hằng số
maxN = 50007. - Mảng
st[]- Lưu thông tin của mỗi nút trên Segment Tree.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 5e4 + 7;
// Thông tin của mỗi nút
struct node {
int pre, suf, sum, maxsum;
static node base() { return { -inf, -inf, 0, -inf }; }
// Hàm hợp nhất 2 nút con
static node merge(const node& a, const node& b) {
node res;
res.pre = max(a.pre, b.pre + a.sum);
res.suf = max(b.suf, a.suf + b.sum);
res.sum = a.sum + b.sum;
res.maxsum = max(a.maxsum, b.maxsum);
res.maxsum = max(res.maxsum, a.suf + b.pre);
return res;
}
};
int n, m;
int a[maxN];
node st[4 * maxN];
// Thủ tục xây dựng cây phân đoạn
void build(int id, int l ,int r) {
if (l == r) {
st[id] = { a[l], a[l], a[l], a[l] };
return;
}
int mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] = node::merge(st[2 * id], st[2 * id + 1]);
}
// Hàm lấy giá trị
node get(int id, int l, int r, int u, int v){
if (l > v || r < u) return node::base();
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
node g1 = get(2 * id, l, mid, u, v);
node g2 = get(2 * id + 1, mid + 1, r, u, v);
return node::merge(g1, g2);
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
cin >> m;
while (m--) {
int x, y;
cin >> x >> y;
cout << get(1, 1, n, x, y).maxsum << '\n';
}
}
¶ Đánh giá
Độ phức tạp
Để xây dựng cây phân đoạn, ta mất độ phức tạp . Với mỗi truy vấn, ta mất thêm độ phức tạp cho mỗi thao tác lấy giá trị trên Segment Tree.
Nhìn chung, độ phức tạp của thuật toán là .
¶ Ví dụ 3
¶ Bài toán
Cho một dãy số có số. Bạn cần xử lí loại truy vấn:
- Truy vấn loại có dạng , ta đổi số ở vị trí thành .
- Truy vấn loại có dạng , ta cần in ra số nhỏ nhất mà lớn hơn bằng trong khoảng .
(với là số lượng truy vấn).
¶ Phân tích
Trong bài toán này, mỗi nút của cây phân đoạn là một multiset chứa các phần tử trong đoạn mà nó quản lí. Khi đó, để hợp nhất các nút con, ta chỉ cần insert toàn bộ phần tử của cả nút con vào nút cha.
Mỗi khi cập nhật cây phân đoạn, nếu ta duyệt từng phần tử của các nút con để insert vào nút cha thì với số lượng truy vấn , ta sẽ mất độ phức tạp lên tới hơn (chưa kể độ phức tạp của các thao tác trên multiset), vì số lượng phần tử của mỗi nút có thể lên tới .
Thay vào đó, ta nhận thấy rằng, khi thay đổi giá trị thành thì tất cả multiset của các nút quản lí phân đoạn chứa phần tử (các nút nằm trên đường đi đơn từ gốc đến nút lá tương ứng) đều sẽ phải xóa đi một giá trị và thêm vào một giá trị . Do đó, với truy vấn loại , khi cập nhật một nút, ta không cần phải insert lại toàn bộ phần tử của cả nút con, mà chỉ cần xóa đi một giá trị cũ trong multiset và chèn thêm giá trị mới.
Với truy vấn loại , ta thực hiện tương tự như thao tác lấy giá trị. Tuy nhiên, mỗi khi xét đến nút mà đoạn nó quản lí nằm hoàn toàn bên trong đoạn cần truy vấn (trường hợp cơ sở), ta sử dụng hàm để trả ra giá trị nhỏ nhất mà vẫn lớn hơn hoặc bằng trong multiset của nút đó.
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
inf = 1000000007. - Hằng số
maxN = 100007. - Mảng
st[]- Lưu thông tin của mỗi nút trên Segment Tree.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 1e5 + 7;
int n, m;
int a[maxN];
multiset <int> st[4 * maxN];
void build(int id, int l, int r) {
if (l == r) {
st[id].insert(a[l]);
return;
}
int mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] = st[2 * id + 1];
for (auto x : st[2 * id]) st[id].insert(x);
}
void update(int id, int l, int r, int i, int old, int val) {
if (l > i || r < i) return;
if (l == r) {
st[id].clear();
st[id].insert(val);
return;
}
int mid = l + r >> 1;
update(2 * id, l, mid, i, old, val);
update(2 * id + 1, mid + 1, r, i, old, val);
st[id].erase(st[id].find(old));
st[id].insert(val);
}
int get(int id, int l, int r, int u, int v, int k) {
if (l > v || r < u) return inf;
if (l >= u && r <= v) {
auto it = st[id].lower_bound(k);
if (it == st[id].end()) return inf;
return *it;
}
int mid = l + r >> 1;
int get1 = get(2 * id, l, mid, u, v, k);
int get2 = get(2 * id + 1, mid + 1, r, u, v, k);
return min(get1, get2);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
while (m--){
int type, l, r, k;
cin >> type;
if (type == 1) {
cin >> l >> k;
update(1, 1, n, l, a[l], k);
a[l] = k;
}
else {
cin >> l >> r >> k;
int ans = get(1, 1, n, l, r, k);
cout << ((ans == inf) ? -1 : ans) << '\n';
}
}
}
¶ Đánh giá
Ngoài ra còn có cách cài đặt khác đơn giản hơn, ta có thể cài đặt hàm update theo cách cập nhật "từ dưới lên trên" (không sử dụng đệ quy) như sau:
- Ta sẽ bắt đầu xuất phát từ nút lá tương ứng với phần tử cần sửa đổi và đi dần lên nút gốc.
void update(int i, int val){
/* leaf[i] là chỉ số của nút lá tương ứng với
phần tử ở vị trí i trong dãy số */
int id = leaf[i];
int old = *st[id].begin();
while (id) {
st[id].erase(st[id].find(old));
st[id].insert(val);
id /= 2;
}
}
Tham khảo code chuẩn tại đây.
Độ phức tạp
Với thao tác xây dựng cây phân đoạn, ta thấy rằng, ở mỗi độ sâu của cây, ta sẽ phải duyệt hết toàn bộ phần tử trong dãy để insert vào multiset của các nút cha.
-
Ví dụ: Xét trường hợp tổng quát, với là lũy thừa của , ta có cây phân đoạn đầy đủ sau:
- Ở độ sâu thứ , mỗi nút là nút lá của cây nên ta có thể lấy trực tiếp giá trị từ các phần tử tương ứng trong dãy số. Vì có nút lá nên ta sẽ mất độ phức tạp .
- Ở độ sâu thứ , để cập nhật giá trị cho nút quản lí đoạn ta sẽ phải duyệt tất cả các phần tử của cả hai nút con, nghĩa là ta sẽ phải duyệt hết các phần tử trong đoạn và . Tương tự với các nút quản lí đoạn , , . Do đó, ta cũng sẽ mất thêm độ phức tạp .
- Ở độ sâu thứ , để cập nhật giá trị cho nút quản lí đoạn ta sẽ phải duyệt tất cả các phần tử của cả hai nút con, nghĩa là ta sẽ phải duyệt hết các phần tử trong đoạn và . Tương tự với nút quản lí đoạn . Do đó, ta cũng sẽ mất thêm độ phức tạp .
- Nhận thấy rằng, với mỗi độ sâu của cây, ta đều phải duyệt lại toàn bộ phần tử trong dãy nên sẽ mất độ phức tạp .
Mà chiều cao của cây là nên thao tác xây dựng cây phân đoạn có độ phức tạp là (độ phức tạp thời gian cho việc chèn, xóa và truy xuất thông tin trên multiset là ).
Với mỗi thao tác cập nhật hoặc lấy giá trị, ta mất độ phức tạp .
Nhìn chung, độ phức tạp của thuật toán là .
¶ Cập nhật lười (Lazy Propagation)
Đây là kĩ thuật được sử dụng trong Segment Tree để giảm độ phức tạp của Segment Tree với các truy vấn cập nhật đoạn.
¶ Ý tưởng
Giả sử ta cần cập nhật đoạn . Dễ thấy rằng, việc cập nhật tất cả các nút trên Segment Tree sẽ mất độ phức tạp rất lớn là (do tổng số phần tử nằm trong đoạn có thể lên đến ). Do đó, với số lượng truy vấn cập nhật đoạn lớn, thao tác này sẽ không đủ tốt.
Vậy nên, trong quá trình cập nhật, ta chỉ thay đổi giá trị ở các nút gần gốc nhất sao cho tổng tất cả các phạm vi mà các nút đó quản lí đúng bằng đoạn .
-
Ví dụ: Cho mảng và ta cần cập nhật đoạn :
- Ta chỉ cập nhật giá trị ở các nút quản lý đoạn và . Giá trị của các nút quản lý đoạn , , , , , , , sẽ không đúng. Ta sẽ chỉ cập nhật lại giá trị của các nút này khi thật sự cần thiết (Do đó kĩ thuật này được gọi là lazy - lười biếng).
Cụ thể, ta xem xét bài toán sau:
¶ Bài toán
Bạn được cho một mảng gồm số nguyên với . Nhiệm vụ của bạn là xử lí loại truy vấn:
- Loại có dạng : Tăng giá trị của các phần tử từ vị trí thứ đến vị trí thứ trong dãy lên đơn vị .
- Loại có dạng : In ra phần tử lớn nhất của dãy từ phần tử thứ đến phần tử thứ .
Với mỗi truy vấn loại , hãy in ra câu trả lời trên một dòng.
(với là số lượng truy vấn).
¶ Phân tích
Ban đầu, ta thực hiện thủ tục xây dựng cây phân đoạn như bình thường.
Truy vấn loại là thao tác lấy giá trị cơ bản trên Segment Tree đã được phân tích trước đó.
Với truy vấn loại , thao tác cập nhật đoạn . Giả sử ta gọi là giá trị lớn nhất trong đoạn mà nút quản lý. Trong lúc cập nhật, muốn hàm này thực hiện với độ phức tạp không quá , thì khi xét đến nút quản lý đoạn mà đoạn nằm hoàn toàn trong đoạn , thì ta không được đệ quy vào các nút con của nó nữa (nếu không độ phức tạp sẽ là do ta đi vào tất cả các nút nằm trong đoạn ).
Để giải quyết, ta dùng kĩ thuật Lazy Propagation như sau:
- Mỗi nút của Segment Tree sẽ lưu thêm một giá trị với ý nghĩa là tất cả các phần tử trong đoạn mà nút quản lý đều được tăng thêm . Nói cách khác, nó sẽ lưu trữ các giá trị cần cập nhật của mỗi nút.
- Ban đầu, ta khởi tạo tất cả các phần tử của mảng bằng . Nếu có nghĩa là không có cập nhật nào đang chờ được xử lý trên nút trong cây phân đoạn. Ngược lại, nếu nghĩa là ta cần cập nhật giá trị của nút theo trước khi thực hiện bất kỳ thao tác nào với nút đó (việc cập nhật này tùy vào mục đích của cây; ví dụ như trong bài toán trên, giá trị của nút sẽ được tăng thêm ).
- Nếu nút đang xét còn có giá trị được thêm vào chưa xét đến (từ các truy vấn cập nhật xảy ra trước đó, mà chưa được cập nhật hết), ta buộc phải cập nhật nó trước khi lấy giá trị hoặc tiếp tục đệ quy sâu hơn. Sau khi cập nhật xong nút , ta phải đẩy giá trị ở nút xuống các con của nó để tiếp tục cập nhật và đặt lại của nút về .
- Để làm được điều này, ở đầu các hàm
getvàupdateta thực hiện các thao tác sau:st[id] += lazy[id]- cập nhật giá trị nút theo .- Nếu nút không phải là nút lá thì ta đẩy giá trị xuống các con của nó :
lazy[2 * id] += lazy[id]lazy[2 * id + 1] += lazy[id]
lazy[id] = 0- chú ý ta cần phải thực hiện thao tác này, nếu không mỗi phần tử của dãy sẽ bị tăng lên nhiều lần, do ta đẩy xuống nhiều lần.
- Bây giờ, để cập nhật đoạn, ta thực hiện tương tự như ở thao tác lấy giá trị, là xác định tập hợp ít nút nhất sao cho tổng tất cả các phạm vi mà các nút đó quản lí đúng bằng đoạn cần cập nhật. Khi đó, ta sửa lại giá trị của các nút thuộc tập hợp này và lưu lại giá trị cần cập nhật vào tương ứng với các nút con của chúng.
¶ Cài đặt
Cấu trúc dữ liệu:
- Hằng số
inf = 1000000007. - Hằng số
maxN = 100007. - Mảng
st[]- Lưu thông tin của mỗi nút trên Segment Tree. - Mảng
lazy[]- Lưu trữ các giá trị cần cập nhật của mỗi nút trên Segment Tree.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxN = 1e5 + 7;
int n, q;
int a[maxN];
long long st[4 * maxN], lazy[4 * maxN];
void build(int id, int l, int r) {
if (l == r) {
st[id] = a[l];
return;
}
int mid = l + r >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
st[id] = max(st[2 * id], st[2 * id + 1]);
}
// Cập nhật nút đang xét và đẩy giá trị lazy xuống các nút con
void fix(int id, int l, int r) {
if (!lazy[id]) return;
st[id] += lazy[id];
// Nếu id không phải là nút lá thì đẩy giá trị xuống các nút con
if (l != r){
lazy[2 * id] += lazy[id];
lazy[2 * id + 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val) {
fix(id, l, r);
if (l > v || r < u) return;
if (l >= u && r <= v) {
/* Khi cài đặt, ta LUÔN ĐẢM BẢO giá trị của nút được cập nhật ĐỒNG THỜI với
giá trị Lazy Propagation. Như vậy sẽ tránh sai sót. */
lazy[id] += val;
fix(id, l, r);
return;
}
int mid = l + r >> 1;
update(2 * id, l, mid, u, v, val);
update(2 * id + 1, mid + 1, r, u, v, val);
st[id] = max(st[2 * id], st[2 * id + 1]);
}
long long get(int id, int l, int r, int u, int v) {
fix(id, l, r);
if (l > v || r < u) return -inf;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
long long get1 = get(2 * id, l, mid, u, v);
long long get2 = get(2 * id + 1, mid + 1, r, u, v);
return max(get1, get2);
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
cin >> q;
while (q--){
int type, l, r, val;
cin >> type >> l >> r;
if (type == 1) {
cin >> val;
update(1, 1, n, l, r, val);
}
else cout << get(1, 1, n, l, r) << '\n';
}
}
¶ Đánh giá
Độ phức tạp
Tương tự như thao tác lấy giá trị, độ phức tạp của thao tác Lazy Propagation là .
Nhìn chung, độ phức tạp của cả bài toán là .
¶ Ví dụ 4
Codeforces - 558E A Simple Task
¶ Bài toán
Cho một chuỗi kí tự độ dài (chỉ chứa các chữ cái tiếng Anh in thường) và truy vấn, mỗi truy vấn có dạng có nghĩa là hãy sắp xếp chuỗi con gồm các kí tự từ đến theo thứ tự không giảm nếu hoặc theo thứ tự không tăng nếu .
In ra chuỗi cuối cùng sau khi đã thực hiện tất cả các truy vấn.
- .