Tác giả: Vũ chipchip Phúc Hoàng
Cho một tập hợp chứa các đường thẳng có dạng , mỗi đường thẳng được biểu diễn bằng một cặp số . Cần thực hiện hai loại thao tác:
Để giải bài toán này, hai cách phổ biến là ứng dụng bao lồi và sử dụng cây Interval Tree lưu đoạn thẳng. Sau đây là những ưu điểm và nhược điểm của IT đoạn thẳng so với bao lồi.
Lưu ý: Ở đây ta giả sử các đường thẳng thêm vào có hệ số tăng dần hoặc giảm dần, bao lồi được biểu diễn bằng stack.
Tóm lại, so với cách ứng dụng bao lồi, sử dụng IT đoạn thẳng là một phương pháp tổng quát hơn nhưng chậm và tốn nhiều bộ nhớ hơn. Sau đây là những phân tích cơ bản về thuật toán.
Xây dựng một cây Interval Tree để quản lí tập các đoạn thẳng, mỗi nút của cây quản lí một khoảng trên trục hoành. Thông tin lưu ở mỗi nút trên cây sẽ là đoạn thẳng đặc trưng cho khoảng nó quản lí. Đoạn thẳng này phải phủ kín khoảng, tức là đoạn có khoảng bao lấy khoảng do nút quản lí (nếu là đường thẳng thì luôn phủ kín khoảng do nút quản lí). Đoạn thẳng được lưu trong nút phải cao hơn tất cả các đoạn khác tại một vị trí nào đó thuộc khoảng (nếu không thì không cần quan tâm đến đoạn đó). Ý nghĩa của việc lưu này là với một query bất kì, đoạn cao nhất sẽ được lưu trong một nút nào đó của cây IT quản lí khoảng chứa . Cách lưu đoạn thẳng này khá trừu trượng, nếu bạn đọc phần này chưa hiểu, nên bỏ qua để xem cách Query và Update trên cây rồi đọc lại phần này sau.
Như vậy, thông tin lưu trên cây IT sẽ được biểu diễn bằng một mảng line, line là một cặp số biểu diễn đường thẳng.
line it[MAXX * 4]; // MAXX là giới hạn trục hoành
Ngoài ra, có thể thêm một vài mảng phụ cần thiết cho IT như low
, high
, leaf
, ...
Ta định nghĩa hàm Get(line d, int x)
cho biết tung độ của điểm thuộc đường thẳng d
tại hoành độ x
.
int Get(line d, int x)
{
return d.a * x + d.b;
}
Ta sẽ trả lời cho query , xem tại hoành độ , tìm tung độ cao nhất của một điểm thuộc một đoạn trong tập. Như đã nói ở trên, IT lưu các đoạn thẳng đảm bảo trong các nút cây quản lí khoảng chứa có một nút lưu đoạn thẳng đạt tung độ cao nhất (làm thế nào để được như vậy thì xem phần Update). Vậy ở đây, muốn trả lời cho query , ta đi từ gốc xuống nút lá quản lí điểm , trên đường đi update đáp số bằng tung độ cao nhất tại điểm của đoạn thẳng do nút đó quản lí.
int Query(int node, int pos)
{
if(low[node] > pos || high[node] < pos)
{
return -oo;
}
res = Get(it[node], pos);
if(low[node] == high[node])
{
return res;
}
res = max(res, Query(node * 2, pos));
res = max(res, Query(node * 2 + 1, pos));
return res;
}
Độ phức tạp:
Thêm một đoạn thẳng vào tập hợp, ta phải thay đổi những nút trên cây IT quản lí khoảng ứng với đoạn thẳng đó. Việc đầu tiên, giống như Update trên cây IT cơ bản, ta phải chia đoạn cần Update ra thành những khoảng IT.
void Update(int node, int l, int h, line val)
{
if(low[node] > h || high[node] < l)
{
return;
}
if(low[node] >= l && high[node] <= h)
{
// Do something
return;
}
Update(node * 2, l, h, val);
Update(node * 2 + 1, l, h, val);
}
Độ phức tạp của phần chia khoảng này là: , giống như IT cơ bản. Nếu đoạn cần Update là đường thẳng thì không mất thời gian chia khoảng, độ phức tạp chỉ là .
Bây giờ việc phải làm là điền vào chỗ // Do Something
. Ta có một đường thẳng val
và đường thẳng it[node]
, cả hai đều chỉ được xét trong khoảng từ low[node]
đến high[node]
. Lấy mid
là điểm giữa của khoảng (mid = (low[node] + high[node]) / 2)
. Ta sẽ thay đổi nút it[node]
và cả các con của nó. Có 6 trường hợp có thể xảy ra:
it[node]
hoàn toàn nằm trên val
. Trường hợp này ta chỉ bỏ qua mà không làm gì, vì val
chắc chắn không bao giờ đạt max trong khoảng low[node]
đến high[node]
.if(Get(it[node], low[node]) >= Get(val, low[node]) && Get(it[node], high[node]) >= Get(val, high[node]))
{
return;
}
it[node]
hoàn toàn nằm dưới val
. Trường hợp này ta gán it[node]
bằng val
, it[node]
cũ không còn giá trị khi tìm max.if(Get(it[node], low[node]) <= Get(val, low[node]) && Get(it[node], high[node]) <= Get(val, high[node]))
{
it[node] = val;
return;
}
it[node]
hoàn toàn nằm trên nửa bên trái của val
. Vậy val
chắc chắn không bao giờ đạt max tại nửa trái của khoảng node
, ta giữ lại it[node]
tại node
và down val
xuống con phải (node * 2 + 1)
.if(Get(it[node], low[node]) >= Get(val, low[node]) && Get(it[node], mid) >= Get(val, mid))
{
Update(node * 2 + 1, l, h, val);
return;
}
it[node]
hoàn toàn nằm dưới nửa bên trái của val
. Tương tự như trên, ta down it[node]
xuống con phải của node và update it[node]
bằng val
.if(Get(it[node], low[node]) <= Get(val, low[node]) && Get(it[node], mid) <= Get(val, mid))
{
Update(node * 2 + 1, l, h, it[node]);
it[node] = val;
return;
}
it[node]
hoàn toàn nằm trên nửa bên phải của val
.if(Get(it[node], mid + 1) >= Get(val, mid + 1) && Get(it[node], high[node]) >= Get(val, high[node]))
{
Update(node * 2, l, h, val);
return;
}
it[node]
hoàn toàn nằm dưới nửa bên phải của val
.if(Get(it[node], mid + 1) <= Get(val, mid + 1) && Get(it[node], high[node]) <= Get(val, high[node]))
{
Update(node * 2, l, h, it[node]);
it[node] = val;
return;
}
Sau khi xét xong 6 trường hợp ở trên, ta đã xử lí xong việc Update đoạn val trong một khoảng low[node]
, high[node]
. Độ phức tạp của thao tác này là , vì có thể phải đi từ node
cho đến lá. Có thể thấy, cây IT có đầy đủ thông tin về đoạn thằng đạt max tại một hoành độ nhất định, vì ta chỉ loại những đoạn thẳng mà hoàn toàn không còn giá trị (trường hợp 1 và trường hợp 2), còn những đoạn thẳng vẫn có thể đạt max tại một vị trí nào đấy luôn được bảo tồn.
Độ phức tạp: . khi chia khoảng, khi update trên một khoảng. Nếu update đường thẳng thì không mất thời gian chia khoảng, độ phức tạp tổng cộng là .
Query và Update ở trên là những thao tác cơ bản nhất của IT đoạn thẳng. Ngoài ra, có thể có thêm nhiều thông tin phụ đính kèm với đoạn thẳng, tùy thuộc vào đề bài toán.
Có nhiều cách để biểu diễn đoạn thẳng trong cây IT ngoài . Ví dụ, có thể biểu diễn đoạn thẳng bằng cách lưu tọa độ 2 điểm đầu mút của đoạn. Tùy vào đề bài toán mà có cách biểu diễn hợp lí nhất.
Bài toán tìm max, min của thường đi kèm với thuật toán quy hoạch động, chẳng hạn như bài toán quy hoạch động có công thức , ta cần tìm sao cho hàm đó đạt max. Bao lồi cũng là phương pháp thường được sử dụng trong bài toán này. Hạn chế của bao lồi là phải tăng dần hoặc giảm dần (nếu không sẽ phải sử dụng cấu trúc khác stack để biểu diễn bao lồi, code rất khó khăn). Hạn chế của IT đoạn thẳng là phải nguyên và nhỏ để có thể biểu diễn trên IT (nếu không sẽ phải sử dụng IT động hoặc rời rạc hóa).
Ngoài ra, có một số bài toán yêu cầu tìm max, min trên tập đoạn thẳng. Đây là những bài toán IT đoạn thẳng gần như là cách làm duy nhất.
Để hiểu rõ về IT đoạn thẳng, bạn hãy tự trả lời một số câu hỏi sau:
Trong trường hợp nào thì một nút không có thông tin gì cả?
Trong các trường hợp 4 và 6 của phần Update, tại sao phải gán lại val
cho it[node]
?
Giả sử thay vì truy vấn theo điểm, ta truy vấn theo khoảng, tức là trả lời xem tại tất cả các điểm trong một khoảng nào đó, đoạn thẳng nào đạt chiều cao lớn nhất / nhỏ nhất. Giả sử khoảng này nằm hoàn toàn trong phạm vi quản lí của một nút nào đó, liệu ta có thể trả luôn kết quả là đoạn thẳng lưu trong nút đó không? Vì sao?
Để làm những bài tập này, đầu tiên ta sẽ giải bằng cách quy hoạch động với độ phức tạp . Công thức quy hoạnh động sẽ có dạng là , với mọi từ 1 đến . Để giảm độ phức tạp xuống , ta sẽ sử dụng bao lồi hoặc IT đoạn thẳng. Lưu ý là với cách bao lồi, stack bao lồi phải đảm bảo tăng dần hoặc giảm dần, nếu không phải lọc ra sao cho tính chất này thỏa mãn. Lưu ý rằng bao lồi chỉ có thể làm được khi hệ số góc tăng dần hoặc giảm dần.
Bài này yêu cầu tìm max và min khi cho điểm bất kì, hay là max và min.
Đây chính là dạng chuẩn của bài toán bao lồi và IT đoạn thẳng. Tuy nhiên làm bao lồi trong trường hợp này cực kì khó khăn, vì hệ số góc không đảm bảo tăng dần hoặc giảm dần. Để có thể làm bao lồi với bài này, ta phải sử dụng cấu trúc dữ liệu lưu bao lồi sao cho hệ số góc vẫn tăng hoặc giảm, cách đơn giản nhất là trong quá trình thêm ta sử dụng một buffer có sức chứa là , khi nào buffer đầy thì gộp vào bao lồi. Lúc query thì tìm max, min trên cả bao lồi và buffer. Solution bao lồi chi tiết xem ở đây.
Còn với IT đoạn thẳng, ta cũng gặp khó khăn vì query không phải là số nguyên, và cũng rất lớn. Tuy nhiên ta có thể xử lí offline đơn giản bằng cách đọc hết tất cả các query, lưu lại các điểm , rời rạc hóa lại, và xây dựng cây IT đoạn thẳng trên tập điểm đã rời rạc hóa đấy. Trong bài này, cách IT đoạn thẳng đơn giản hơn nhiều so với cách bao lồi.
Bài "độc quyền" của IT đoạn thẳng. Trong bài này, ta cũng tìm công thức quy hoạch động : .
Tuy nhiên, đáng lưu ý là mỗi cặp chỉ được tính trong một khoảng nào đó, còn nằm ngoài khoảng đó thì cặp này không được phép chọn để lấy max. Đây chính là tính chất "đoạn thẳng" thay vì "đường thẳng". Bài này không thể sử dụng bao lồi để giải được.