¶ Li-chao Tree (Cây phân đoạn trên tập đường thẳng)
Tác giả:
- Nguyễn Tấn Minh - THPT Chuyên Lê Hồng Phong, TPHCM.
Reviewer:
- Đoàn Gia Huy - HUS High School for Gifted Students
- Nguyễn Quang Minh - HUS High School for Gifted Students
¶ Giới thiệu
Li-chao tree (cây phân đoạn trên tập đường thẳng) là một biến thể của Segment tree[1] (cây phân đoạn) cho phép quản lý một tập đường thẳng với thao tác sau:
- Thêm một hàm vào tập đường thẳng.
- Cho một số nguyên (với ), gọi là tập đường thẳng hiện tại, tính hoặc .
Cả hai thao tác trên đều có thể được xử lý trong .
Tổng quát hơn, Li-chao tree có thể xử lý những loại hàm có tính chất sau:
Gọi và là hai hàm bất kì thuộc loại này sao cho và xác định trên khoảng đang xét. Hai hàm này cần thỏa một trong hai tính chất:
- Nếu thì với và .
- Nếu thì với và .
Hoặc ta cũng có thể biến đổi điều kiện này thành cắt tại tối đa điểm.
Trong bài viết này, ta chỉ quan tâm đến phương trình đường thẳng, loại phương trình thỏa tính chất nêu trên:
Ngoài ra, ta giả sử thao tác loại sẽ thực hiện tìm , thao tác tìm được thực hiện tương tự.
¶ Ý tưởng
¶ Đường thẳng và tính chất của phương trình đường thẳng
Trong toán học, ta đã biết một đường thẳng có thể biểu diễn dưới dạng một phương trình tuyến tính bậc có dạng . Trong đó:
- Hệ số góc hay độ dốc (slope) thể hiện mức độ tăng/giảm nhanh/chậm của hàm. Ví dụ, hàm tăng nhanh hơn hàm do có hệ số dốc lớn hơn. Tương tự, hàm giảm nhanh hơn hàm do có hệ số góc bé hơn.
- Hệ số tự do (y-intercept) cho biết phương trình cắt trục tại điểm .
¶ Tính chất của tập đường thẳng
Nếu vẽ một tập đường thẳng bất kì ra, ta thấy những đoạn đóng góp vào đáp án, tạm gọi là "min-line", sẽ tạo thành nửa trên của một bao lồi[2] (upper hull) như sau:
Mỗi đường thẳng đóng góp vào min-line duy nhất một đoạn liên tiếp và từ trái qua phải, thứ tự xuất hiện của các đường thẳng là thứ tự giảm dần theo hệ số góc của chúng. Một số đường thẳng có thể không đóng góp gì vào min-line.
Đối với max-line thì sao?
Max-line sẽ tạo thành nửa dưới của một bao lồi (lower hull), với các đường thẳng đóng góp vào max-line từ trái qua phải là thứ tự tăng dần theo hệ số góc.
¶ Xây dựng mảng
Giả sử ta có mảng gồm phần tử với là đường thẳng đóng góp vào min-line tại . Với nhận xét được nêu trên, khi thêm một đường thẳng vào tập, có thể thấy một số giá trị liên tiếp sẽ được gán cho đường thẳng mới.
Ví dụ, sau đây là ảnh minh họa cho mảng quản lý một upper hull tại các vị trí .
Lưu ý
Chúng ta phải lưu cả phương trình đường thẳng thay vì chỉ đơn giản là giá trị của hàm tại điểm đó. Nếu chỉ lưu giá trị của hàm tại điểm , thao tác cập nhật sẽ không còn đơn giản là gán một đoạn cho cùng một phương trình đường thẳng, mà là gán giá trị theo bậc thang.
Đến đây, ta có thể liên tưởng đến Segment tree để xử lý cập nhật đoạn (range update) và truy cập điểm (point access), sử dụng lazy propagation. Tuy nhiên, đối với Li-chao tree, ta sẽ phải làm khác đi một chút so với Segment tree truyền thống.
¶ Ôn lại Segment tree
Trước khi đi đến ý tưởng của Li-chao, ta sẽ tìm hiểu cách sử dụng Segment tree để xử lý bài toán sau. Cho mảng gồm phần tử và truy vấn thuộc một trong hai loại:
- Cho ba số nguyên , gán đối với mọi thỏa .
- Cho số nguyên , tính .
Đối với dạng bài toán này, chúng ta có thể xây dựng Segment tree chỉ có mảng lazy và không cần bước push-down như sau:
- Đối với truy vấn loại , tách đoạn thành đoạn (theo ý tưởng Segment tree truyền thống) và cập nhật những nút tương ứng.
- Đối với truy vấn loại , lấy của các nút quản lý vị trí , tức là đường đi từ gốc xuống nút lá tương ứng.
Code tham khảo
void update (int a, int b, int x, int k, int l, int r) {
/*
a..b: khoảng cần cập nhật
x: giá trị cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
if (b < l || r < a) return;
if (a <= l && r <= b) {
lazy[k] = min(lazy[k], x);
return;
}
int mid = (l + r) >> 1;
update(a, b, x, 2 * k, l, mid);
update(a, b, x, 2 * k + 1, mid + 1, r);
}
int query (int p, int k, int l, int r) {
/*
p: vị trí được truy vấn
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
int ans = lazy[k], mid = (l + r) >> 1;
if (l == r) return ans;
if (p <= mid)
return min(ans, query(p, 2 * k, l, mid));
else return min(ans, query(p, 2 * k + 1, mid + 1, r));
}
Bây giờ, ta sẽ tìm cách biển đổi cách xử lý trên để áp dụng cho tập đường thẳng.
¶ Thuật toán
¶ Thao tác loại : Thêm đường thẳng
Đầu tiên, đưa đường thẳng mới vào nút gốc của Li-chao tree. Tại mỗi nút , gọi:
- là hàm được đưa vào.
- là hàm mà nút đang chứa.
- là đoạn mà nút quản lý, .
- là đoạn mà hàm sẽ đóng góp vào min-line (ta chưa biết đoạn này là gì).
Ta thực hiện chia để trị[3] với trường hợp chính như sau:
¶ Trường hợp 1
Khi đó, đoạn chỉ nằm ở một trong hai khoảng hoặc . Đồng nghĩa với việc hàm không thay đổi và hàm sẽ được đưa xuống cây con. Để chọn cây con cho hàm , ta cần so sánh hệ số góc của so với , cụ thể:
- Nếu hệ số góc của lớn hơn , hàm sẽ được đưa xuống cây con bên trái và chia để trị tiếp cho đoạn tương ứng là .
- Nếu hệ số góc của bé hơn , hàm sẽ được đưa xuống cây con bên phải và chia để trị tiếp cho đoạn tương ứng là .
- Nếu hệ số góc của và bằng nhau, khi đó đường thẳng nằm song song và ở phía trên nên chắc chắn sẽ không đóng góp gì vào min-line. Ta có thể không làm gì cả hoặc gộp trường hợp này vào một trong hai trường hợp nêu trên.
¶ Trường hợp 2
Khi đó, đoạn nằm ở cả hai khoảng và . Đồng nghĩa với việc hàm sẽ bị thay thế bởi hàm . Ta gán bằng , thao tác này tương đương với gán cho đoạn
Lưu ý
Tuy phép gán cho cả đoạn có thể sẽ thừa so với đoạn nhưng ta đang thao tác với hàm / nên điều này không làm ảnh hưởng kết quả.
Đường thẳng ban đầu vẫn còn có thể đóng góp vào min-line ở một trong hai khoảng hoặc . Do đó, ta đưa đường thẳng này xuống một trong hai cây con. Việc chọn cây con tương tự trường hợp 1 nhưng bây giờ hàm và đổi vai trò cho nhau.
¶ Xử lý tổng quát
Trên thực tế, ta có thể giảm số trường hợp cần xử lý bằng một trong hai cách:
- Quy ước .
- Quy ước hệ số góc của lớn hơn hoặc bằng .
Nếu điều kiện quy ước không được thỏa, ta chỉ việc tráo đổi hai đường thẳng cho nhau. Trong bài viết này, mình sẽ sử dụng cách làm đầu tiên.
Ngoài ra, để tránh phải xử lý nửa khoảng khi chia để trị, nếu ta chỉ quan tâm các vị trí là số nguyên, ta sẽ chia khoảng thành và thay vì và như trên, với .
Tương tự, nếu ta quan tâm cả những vị trí là số thực, ta có thể chia đoạn thành và với và là hằng số nhỏ khoảng đến lần sai số tổi thiểu (thường là hoặc ).
Như vậy, ta có thể hiểu rằng là đường thẳng tối ưu cho vị trí , nếu chưa tính các đường thẳng được lưu tại các nút tổ tiên của .
¶ Trường hợp cơ sở (base case)
Quá trình chia để trị sẽ kết thúc khi ta đi xuống đến nút lá, khi đó, ta chỉ việc so sánh hai hàm và xem hàm nào tốt hơn cho vị trí tương ứng rồi gán cho hàm tối ưu.
¶ Thao tác loại : Tìm hàm tối ưu cho điểm
Tương tự với Segment tree, để lấy dữ liệu cho vị trí , ta kết hợp dữ liệu ở các nút quản lý . Nói cách khác, ta sẽ thực hiện di chuyển từ gốc của Li-chao tree xuống nút lá tương ứng với vị trí và lấy đường thẳng tối ưu nhất trên đường đi.
¶ Cài đặt
¶ Li-chao tree cho tập đường thẳng
Để thuận tiện cho việc cài đặt, ta cần tạo ra một struct biểu diễn đường thẳng.
struct line {
ll a, b;
line() : a(0), b(0) {}
line (ll a, ll b) : a(a), b(b) {}
ll calc (ll x) { return a * x + b; }
ll slope() { return a; }
};
Ban đầu, tất cả các nút của Li-chao tree chứa đường thẳng (tức là đường thẳng song song với trục nằm rất cao). Ở đây mình chọn vô cực là LLONG_MAX.
struct liChao {
vector<line> tr;
liChao() {}
liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}
void update (line f, int k, int l, int r) {
/*
f: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
if (l == r) {
tr[k] = (f.calc(l) < tr[k].calc(l) ? f : tr[k]);
return;
}
int mid = (l + r) >> 1;
// để giảm số trường hợp cần xử lý, giả sử tr[k] tốt hơn f cho vị trí mid
if (f.calc(mid) < tr[k].calc(mid)) swap(tr[k], f);
// trường hợp 1.1, đường thẳng f được đưa xuống cây con trái
if (f.slope() > tr[k].slope())
update(f, 2 * k, l, mid);
// trường hợp 1.2, đường thẳng f được đưa xuống cây con phải
if (f.slope() < tr[k].slope())
update(f, 2 * k + 1, mid + 1, r);
}
ll query (int pos, int k, int l, int r) {
/*
pos: vị trí được truy vấn
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
ll cur = tr[k].calc(pos);
int mid = (l + r) >> 1;
// thực hiện di chuyển từ nút gốc xuống nút lá tương ứng, tương tự như Segment tree
if (l == r) return cur;
if (pos <= mid)
return min(cur, query(pos, 2 * k, l, mid));
else return min(cur, query(pos, 2 * k + 1, mid + 1, r));
}
};
Đánh giá độ phức tạp:
- Thời gian: cho mỗi thao tác.
- Bộ nhớ: cho cả Li-chao tree.
¶ Li-chao tree tổng quát
Khi cài đặt Li-chao tree cho các hàm không phải phương trình đường thẳng, ta không thể chọn cây con để đưa hàm xuống bằng cách so sánh hệ số góc nữa. Lúc này, ta sử dụng điều kiện tổng quát:
- Nếu thì hàm sẽ được đưa xuống cây con trái.
- Nếu thì hàm sẽ được đưa xuống cây con phải.
void update (line f, int k, int l, int r) {
if (l == r) {
tr[k] = (f.calc(l) < tr[k].calc(l) ? f : tr[k]);
return;
}
int mid = (l + r) >> 1;
if (f.calc(mid) < tr[k].calc(mid)) swap(tr[k], f);
if (f.calc(l) < tr[k].calc(l))
update(f, 2 * k, l, mid);
if (f.calc(r) < tr[k].calc(r))
update(f, 2 * k + 1, mid + 1, r);
}
Các hàm còn lại vẫn sẽ được cài đặt như cũ. Lưu ý rằng, khi cài đặt như thế này, chúng ta cần để ý để hằng số cho việc tính toán các hàm, vì chúng được gọi khá nhiều.
¶ Mở rộng: Các tối ưu và biến thể Li-chao tree
¶ Tối ưu bộ nhớ
Đối với Li-chao tree kinh điển, ta có thể tối ưu bộ nhớ một chút bằng cách định nghĩa lại cách chia để trị. Cụ thể, với một nút quản lý đoạn :
- Nút con bên trái quản lý đoạn .
- Nút con bên phải quản lý đoạn .
Với cách làm này, không khó để chứng minh rằng ta chỉ cần đúng nút cho Li-chao tree và việc đánh số cũng trở nên dễ dàng hơn khi ta có thể dùng là chỉ số cho các nút.
Code tham khảo
struct liChao {
vector<line> tr;
liChao() {}
liChao (int sz) : tr(sz + 1, line(0, LLONG_MAX)) {}
void update (line f, int l, int r) {
/*
f: đường thẳng cần cập nhật
mid: nút hiện tại
l..r: khoảng mà nút quản lý
*/
if (l > r) return;
int mid = (l + r) >> 1;
if (l == r) {
tr[mid] = (f.calc(l) < tr[mid].calc(l) ? f : tr[mid]);
return;
}
// việc cập nhật được thực hiện tương tự Li-chao tree cơ bản
if (f.calc(mid) < tr[mid].calc(mid)) swap(tr[mid], f);
if (f.slope() > tr[mid].slope())
update(f, l, mid - 1); // trường hợp 1.1
if (f.slope() < tr[mid].slope())
update(f, mid + 1, r); // trường hợp 1.2
}
ll query (int p, int l, int r) {
/*
p: vị trí được truy vấn
mid: nút hiện tại
l..r: khoảng mà nút quản lý
*/
int mid = (l + r) >> 1;
ll cur = tr[mid].calc(p);
if (p == mid) return cur;
if (p < mid) return min(query(p, l, mid - 1), cur);
if (p > mid) return min(query(p, mid + 1, r), cur);
}
};
Lưu ý, với cách cài đặt này, một base case mới sẽ phát sinh đó là hàm update sẽ được gọi với . Ví dụ, khi được gọi với đoạn , hàm sẽ chia thành đoạn và .
Hiệu quả của tối ưu có thể được thể hiện qua bài Building Bridges (CEOI 2017)[4] như sau:
| Solution | Thời gian chạy | Bộ nhớ |
|---|---|---|
| Chưa tối ưu | 70 mili giây | 66540 kB |
| Đã tối ưu | 56 mili giây | 19564 kB |
Các bạn có thể tham khảo code của mình tại đây.
¶ Li-chao tree cho tập đoạn thẳng
Ta có thể biến đổi Li-chao tree để xử lý tập đoạn thẳng với thao tác như sau:
- Cho bốn số nguyên , thêm đoạn thẳng với vào tập đoạn thẳng.
- Cho một số nguyên (với ), gọi là tập đường thẳng hiện tại, tính .
Bài toán này khác bài toán gốc ở chỗ, thay vì phải xử lý đường thẳng, ta phải xử lý đoạn thẳng, tức là:
Tập đoạn thẳng bấy giờ không còn là nửa trên của bao lồi nữa. Tuy nhiên, với truy vấn loại , ta có thể chia đoạn thành đoạn (theo ý tưởng của Segment tree) rồi thực hiện thao tác cập nhật của Li-chao tree bắt đầu từ các nút tương ứng. Tổng độ phức tạp thời gian là .
Lưu ý
Đối với biến thể Li-chao tree này, ta không thể sử dụng tối ưu bộ nhớ.
Truy vấn loại được xử lý bình thường trong .
Code tham khảo
struct liChao {
vector<line> tr;
liChao() {}
liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}
void addLine (line f, int k, int l, int r) {
/*
f: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
if (l == r) {
tr[k] = (f.calc(l) < tr[k].calc(l) ? f : tr[k]);
return;
}
int mid = (l + r) >> 1;
if (f.calc(mid) < tr[k].calc(mid)) swap(tr[k], f);
if (f.slope() > tr[k].slope())
addLine(f, 2 * k, l, mid); // trường hợp 1.1
if (f.slope() < tr[k].slope())
addLine(f, 2 * k + 1, mid + 1, r); // trường hợp 1.2
}
void update (int a, int b, line f, int k, int l, int r) {
/*
a..b: khoảng cần cập nhật
f: đường thẳng cần nhập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
if (b < l || r < a) return;
// thực hiện thao tác cập nhật của Li-chao tree cơ bản
// khi khoảng mà nút quản lý nằm gọn trong khoảng cần cập nhật
if (a <= l && r <= b) return addLine(f, k, l, r), void();
// chia để trị tương tự Segment tree
int mid = (l + r) >> 1;
update(a, b, f, 2 * k, l, mid);
update(a, b, f, 2 * k + 1, mid + 1, r);
}
ll query (int pos, int k, int l, int r) {
/*
pos: vị trí được truy vấn
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
ll cur = tr[k].calc(pos);
int mid = (l + r) >> 1;
if (l == r) return cur;
if (pos <= mid)
return min(cur, query(pos, 2 * k, l, mid));
else return min(cur, query(pos, 2 * k + 1, mid + 1, r));
}
};
¶ Li-chao tree trên mảng thưa (Sparse Li-chao tree)
Tương tự Sparse Segment tree[5], chúng ta cũng có thể sử dụng Li-chao tree trên mảng thưa sử dụng con trỏ. Cụ thể, khi quá lớn (ví dụ: ), việc sử dụng bộ nhớ là không thể. Khi đó, ta chỉ tạo các nút cho Li-chao mỗi khi cần cập nhật một nút chưa được tạo.
Có thể thấy, mỗi thao tác cập nhật sẽ thêm vào nút mới. Do đó, độ phức tạp bộ nhớ của Sparse Li-chao tree sau thao tác cập nhật là .
Thao tác truy vấn / thực hiện như bình thường, cần lưu ý tránh truy cập vào con trỏ nullptr.
Code tham khảo
const int M = 1e9;
struct node {
line tr;
node *lpt, *rpt;
node() : tr(0, LLONG_MAX), lpt(nullptr), rpt(nullptr) {}
int divi (int a, int b) { // phép chia làm tròn xuống
return a / b - ((a ^ b) < 0 && a % b);
}
void update (line f, int l = -M, int r = M) {
/*
f: đường thẳng cần cập nhật
l..r: khoảng mà nút quản lý
*/
if (l == r) {
tr = (f.calc(l) < tr.calc(l) ? f : tr);
return;
}
int mid = divi(l + r, 2);
if (f.calc(mid) < tr.calc(mid)) swap(tr, f);
if (f.slope() > tr.slope()) {
if (lpt == nullptr) lpt = new node(); // khởi tạo bộ nhớ cho cây con trái
lpt->update(f, l, mid); // trường hợp 1.1
}
if (f.slope() < tr.slope()) {
if (rpt == nullptr) rpt = new node(); // khởi tạo bộ nhớ cho cây con phải
rpt->update(f, mid + 1, r); // trường hợp 1.2
}
}
ll query (int pos, int l = -M, int r = M) {
/*
pos: vị trí được truy vấn
l..r: khoảng mà nút quản lý
*/
ll cur = tr.calc(pos);
int mid = divi(l + r, 2);
if (l == r) return cur;
// lưu ý: chỉ được di chuyển xuống cây con khi nó được khởi tạo bộ nhớ sẵn
if (pos <= mid)
return min(cur, lpt == nullptr ? LLONG_MAX : lpt->query(pos, l, mid));
else
return min(cur, rpt == nullptr ? LLONG_MAX : rpt->query(pos, mid + 1, r));
}
};
Lưu ý, khi tính cho số âm, ta cần viết lại hàm chia làm tròn xuống.
¶ Tìm hàm tối ưu thứ trên Li-chao tree
Ở những phần trên, chúng ta đã tìm hiểu cách tìm đường thẳng tối ưu nhất cho một vị trí bất kỳ. Với Li-chao tree, ta còn có thể tìm đường thẳng tối ưu thứ . Cụ thể hơn, ta có thể biến đổi Li-chao tree để hỗ trợ hai loại thao tác sau:
- Thêm một hàm vào tập đường thẳng.
- Cho một số nguyên (với ) và (với không quá kích thước tập đường thẳng). Gọi là tập đường thẳng hiện tại, tìm phần tử thứ trong dãy sau khi đã sắp xếp tăng dần.
¶ Ý tưởng
Thoạt đầu, ta sẽ nghĩ đến cách lưu đường thẳng tối ưu nhất ở mỗi nút. Khi số đường thẳng được lưu tại một nút vượt quá , ta sẽ lấy đường thẳng tệ nhất đưa xuống một trong hai cây con.
Tuy nhiên, sẽ có một số trường hợp đường thẳng tệ nhất này còn phải đưa xuống cả hai cây con, ví dụ, với trường hợp sau:
Như vậy, phải lưu bao nhiêu đường thẳng mới đủ?
Ta biết rằng, khi một đường thẳng nằm dưới tại , nó sẽ nằm dưới trong khoảng hoặc .
Xét nút đang bị thừa một đường thẳng, gọi là số đường thẳng nằm dưới đường thẳng tệ nhất trong khoảng , là số đường thẳng nằm dưới đường thẳng tệ nhất trong khoảng . Dễ thấy, để đường thẳng tệ nhất này không được đưa xuống cây con trái thì . Tương tự, để đường thẳng tệ nhất không được đưa xuống cây con phải thì .
Ta muốn đường thẳng tệ nhất này chỉ được đưa xuống tối đa một nút con giống như cơ chế hoạt động của Li-chao tree truyền thống. Do đó, một trong hai giá trị hoặc phải , tức bài toán của chúng ta bây giờ là cực tiểu hóa sao cho .
Không khó để chứng minh câu trả lời là .
¶ Thuật toán
Như vậy, với mỗi nút của Li-chao tree, ta sẽ lưu một danh sách giữ lại đường thẳng tốt nhất (có giá trị bé nhất) được đưa vào. Khi đưa một đường thẳng vào nút, nếu số lượng nút trong danh sách lên đến , ta chọn đường thẳng tệ nhất (có giá trị lớn nhất) rồi đưa xuống một trong hai cây con:
- Trong đường thẳng còn lại, nếu số đường thẳng có hệ số góc lớn hơn đường thẳng tệ nhất là nhỏ hơn , ta đưa đường thẳng tệ nhất xuống cây con trái.
- Trong đường thẳng còn lại, nếu số đường thẳng có hệ số góc bé hơn đường thẳng tệ nhất là nhỏ hơn , ta đưa đường thẳng tệ nhất xuống cây con phải.
Để lấy đường thẳng tối ưu thứ tại vị trí , ta đi từ gốc xuống nút lá tương ứng của vị trí và duy trì một danh sách chứa đường thẳng tốt nhất.
Như vậy, độ phức tạp thời gian cho mỗi thao tác cập nhật và truy vấn là . Độ phức tạp bộ nhớ là với là số đường thẳng được đưa vào.
¶ Cài đặt
Để thuận tiện cho việc cài đặt, mình sử dụng hàm nth_element giúp sắp xếp lại mảng sao cho phần tử ở vị trí thứ sẽ nằm đúng vị trí của nó nếu mảng được sắp xếp, những phần tử còn lại được xếp ngẫu nhiên. Hàm này tốn độ phức tạp gần tuyến tính.
Lưu ý, với cách cài đặt này, danh sách các đường thẳng trong một nút sẽ không được sắp xếp theo thứ tự tối ưu.
Code tham khảo
struct liChao {
vector<vector<line>> tr;
int mkth;
liChao (int sz, int k) : tr(4 * sz), mkth(k) {}
void update (line cur, int k, int l, int r) {
/*
cur: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
tr[k].push_back(cur);
if (tr[k].size() <= 2 * mkth - 1) return;
// chèn đường thẳng mới vào và đưa đường thẳng tệ nhất ra ngoài
int mid = (l + r) >> 1;
nth_element(tr[k].begin(), tr[k].end() - 1, tr[k].end(),
[&] (line a, line b) {return a.calc(mid) < b.calc(mid);}); // đưa đường thẳng tệ nhất ra cuối vector
line worst = tr[k].back();
tr[k].pop_back();
if (l == r) return;
// đếm số đường thẳng được lưu ở nút hiện tại mà tốt hơn đường thẳng tệ nhất
// trong khoảng [l; mid], bằng cách so sánh hệ số góc của chúng
int dominateLeft = 0;
for (line it : tr[k])
dominateLeft += it.slope() > worst.slope();
// đường thẳng tệ nhất được đưa xuống cây con có
// số đường thẳng tốt hơn nó ít hơn "mkth"
if (dominateLeft < mkth) update(worst, 2 * k, l, mid);
else update(worst, 2 * k + 1, mid + 1, r);
}
void push (vector<ll> &cand, ll val, int kth) {
// thêm một giá trị vào vector và giữ lại k giá trị tốt nhất
cand.push_back(val);
if (cand.size() > kth) {
nth_element(cand.begin(), cand.end() - 1, cand.end());
cand.pop_back();
}
}
void walk (vector<ll> &cand, int pos, int kth, int k, int l, int r) {
/*
cand: vector để duy trì k giá trị tốt nhất
pos: vị trí được truy vấn
kth: thứ hạng của đường thẳng cần tìm
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
for (line cur : tr[k]) push(cand, cur.calc(pos), kth);
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid)
walk(cand, pos, kth, 2 * k, l, mid);
else walk(cand, pos, kth, 2 * k + 1, mid + 1, r);
}
ll query (int pos, int kth, int k, int l, int r) {
/*
pos: vị trí được truy vấn
kth: thứ hạng của đường thẳng cần tìm
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
vector<ll> cand;
walk(cand, pos, kth, k, l, r);
nth_element(cand.begin(), cand.end() - 1, cand.end());
return cand.back();
}
};
¶ Lazy propagation trên Li-chao tree (Extended Li-chao tree)
Tương tự với Segment tree, chúng ta hoàn toàn có thể áp dụng Lazy propagation với Li-chao tree, tạo ra những cấu trúc dữ liệu mạnh có thể hỗ trợ những thao tác mà chỉ có Extended Li-chao tree mới làm được.
¶ Bài toán 1
Cho một mảng kích thước và truy vấn online thuộc một trong ba dạng:
- Chèn đoạn thẳng: Cho bốn số nguyên , gán với mọi .
- Tăng đoạn theo dạng bậc thang: Cho bốn số nguyên , tăng lên đơn vị, với mọi .
- Truy vấn điểm: Cho số nguyên , trả về .
Giới hạn:
- .
- .
Với thao tác loại và , chúng ta có thể cài đặt tương tự Li-chao tree quản lý đoạn thẳng như trên. Bây giờ, chúng ta sẽ tìm cách xử lý thao tác loại với Li-chao tree.
¶ Tính chất của phép tăng đoạn theo dạng bậc thang
Ta đã biết, một thao tác tăng theo dạng bậc thang có thể biểu diễn dưới dạng một phương trình đường thẳng, tạm gọi là hàm cập nhật. Hơn nữa, tổng của hai phương trình đường thẳng, cũng là một phương trình đường thẳng. Cụ thể, với hàm và , tổng của chúng là hàm .
Như vậy, ta có thể tưởng tượng một thao tác tăng đoạn theo dạng bậc thang lên một đoạn thẳng chính là "bẻ gãy" đoạn thẳng này tại điểm rồi thay đoạn ở giữa thành tổng của nó và hàm cập nhật.
¶ Ý tưởng
Với Li-chao tree truyền thống, khi chèn một đường thẳng, ta có thể gán nó cho một đoạn rộng hơn đoạn mà đường này thật sự đóng góp và min-line. Điều này không phải là vấn đề với hàm .
Tuy nhiên, khi làm việc với phép cộng, ta chỉ được phép gây ảnh hưởng lên đúng đoạn mà nó được phép gây ảnh hưởng. Để giải quyết vấn đề này, ta sử dụng lazy propagation trên Li-chao tree.
Tương tự lazy propagation trên Segment tree, với mỗi nút, ta lưu lại hàm cập nhật , đại diện cho cả đoạn mà nút quản lý đang được cộng thêm hàm . Mỗi thao tác loại tương đương với việc cộng thêm hàm cập nhật cho nút. Các giá trị chỉ được đưa xuống cây con khi ta cần xử lý đến.
Cần lưu ý, khi đi từ gốc xuống để tìm các nút cần cập nhật đối với truy vấn loại , ta cần đẩy tất cả các đường thẳng còn đang chứa ở các nút xuống bằng một thao tác chèn đoạn thẳng (trong code tham khảo gọi là thao tác pushLine). Điều này sẽ đảm bảo tất cả các đường thẳng nằm trong đoạn cần được tăng sẽ được tăng.
Bên cạnh đó, cần đảm bảo rằng khi thực hiện thao tác loại trên nút nào thì nút đó không chịu ảnh hưởng của bất kỳ giá trị lazy nào.
Code tham khảo
struct line {
ll a, b;
line() : a(0), b(0) {}
line (ll a, ll b) : a(a), b(b) {}
ll calc (ll x) { return (b == LLONG_MAX ? LLONG_MAX : a * x + b); }
ll slope() { return a; }
ll add (ll a, ll b) { // phép cộng chống tràn số
return (max(a, b) == LLONG_MAX ? LLONG_MAX : a + b);
}
void operator += (line o) {
a = add(a, o.a), b = add(b, o.b);
}
};
struct liChao {
vector<line> tr, lazy;
liChao() {}
liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)), lazy(4 * sz) {}
void apply (int k, line f) {
tr[k] += f, lazy[k] += f;
}
void pushDown (int k) {
// đẩy "hàm cập nhật" theo cập nhật tăng đoạn xuống các cây con
// để tránh ảnh hưởng của cập nhật chèn đường thẳng
if (!lazy[k].a && !lazy[k].b) return;
apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]);
lazy[k] = line(0, 0);
}
void insertLine (line f, int k, int l, int r) {
/*
f: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
// thực hiện cập nhật đường thẳng như Li-chao tree cơ bản, thêm
// thao tác "pushDown" để không cập nhật đè lên các cập nhật tăng đoạn
if (l == r) {
tr[k] = (f.calc(l) < tr[k].calc(l) ? f : tr[k]);
return;
}
pushDown(k);
int mid = (l + r) >> 1;
if (f.calc(mid) < tr[k].calc(mid)) swap(tr[k], f);
if (f.slope() > tr[k].slope())
insertLine(f, 2 * k, l, mid);
else if (f.slope() < tr[k].slope())
insertLine(f, 2 * k + 1, mid + 1, r);
}
void pushLine (int k, int l, int r) {
// đẩy hàm của Li-chao tree xuống các cây con để tránh
// ảnh hưởng của cập nhật tăng đoạn
int mid = (l + r) >> 1;
if (tr[k].b != LLONG_MAX) {
insertLine(tr[k], 2 * k, l, mid);
insertLine(tr[k], 2 * k + 1, mid + 1, r);
tr[k] = line(0, LLONG_MAX);
}
}
void updateInsert (int a, int b, line f, int k, int l, int r) {
/*
a..b: khoảng cần cập nhật
f: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
// thực hiện cập nhật đoạn thẳng như Li-chao tree cơ bản, thêm
// thao tác "pushDown" để không cập nhật đè lên các cập nhật tăng đoạn
if (b < l || r < a) return;
if (a <= l && r <= b)
return insertLine(f, k, l, r), void();
pushDown(k);
int mid = (l + r) >> 1;
updateInsert(a, b, f, 2 * k, l, mid);
updateInsert(a, b, f, 2 * k + 1, mid + 1, r);
}
void updateIncrease (int a, int b, line f, int k, int l, int r) {
/*
a..b: khoảng cần cập nhật
f: đường thẳng cần cập nhật
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
// thực hiện cập nhật đoạn tương tự Segment tree, thêm thao tác
// "pushDown" và "pushLine" để không cập nhật đè lên các cập nhật trước đó
if (b < l || r < a) return;
if (a <= l && r <= b)
return apply(k, f), void();
pushDown(k), pushLine(k, l, r);
int mid = (l + r) >> 1;
updateIncrease(a, b, f, 2 * k, l, mid);
updateIncrease(a, b, f, 2 * k + 1, mid + 1, r);
}
ll query (int pos, int k, int l, int r) {
/*
pos: vị trí được truy vấn
k: nút hiện tại
l..r: khoảng mà nút quản lý
*/
ll cur = tr[k].calc(pos);
int mid = (l + r) >> 1;
if (l == r) return cur;
pushDown(k);
if (pos <= mid)
return min(cur, query(pos, 2 * k, l, mid));
else return min(cur, query(pos, 2 * k + 1, mid + 1, r));
}
};
Như vậy, ta có thể xử lý các thao tác trong độ phức tạp lần lượt là , và .
¶ Bài toán 2
Cho một mảng kích thước và truy vấn online thuộc một trong ba dạng:
- Chèn đoạn thẳng: Cho bốn số nguyên , gán với mọi .
- Tăng đoạn: Cho ba số nguyên , tăng lên đơn vị, với mọi .
- Truy vấn đoạn: Cho hai số nguyên , tính .
¶ Ý tưởng
Kết hợp với ý tưởng lazy propagation như trên, bây giờ với mỗi nút, ta lưu thêm một giá trị với là đoạn mà nút quản lý.
Lưu ý, với cách làm này, ta không thể thực hiện thao tác tăng đoạn thao dạng bậc thang, vì việc tăng như thế sẽ làm thay đổi mối quan hệ lớn bé giữa các giá trị trong đoạn được tăng. Tuy nhiên, khi đoạn được tăng cho cùng một giá trị, ta chỉ việc tăng và hệ số tự do của các đoạn thẳng nằm trong đoạn được cập nhật cho cùng một giá trị.
¶ Ứng dụng: Quy hoạch động
Đối với mỗi bài toán trong phần ứng dụng, mình khuyên các bạn đọc giả nên tự suy nghĩ lời giải cho bài toán trước khi đọc tiếp
Bên cạnh các bài toán thuần cấu trúc dữ liệu, Li-chao tree còn có một ứng dụng rất quan trọng đó là cải tiến một số thuật toán Quy hoạch động.
Thông thường, Li-chao tree có thể cải tiến các bài toán QHĐ có công thức truy hồi có dạng:
Trong đó, là các giá trị được xác định từ và các hệ số liên quan.
Để dễ hình dung hơn, chúng ta sẽ tìm hiểu các ví dụ Quy hoạch động kết hợp Li-chao tree sau.
¶ CEOI 2017: Building Bridges
Cho cột đá có độ cao và chi phí tháo dỡ là . Chọn ra một số cột đá để xây dựng cầu với chi phí là tổng bình phương của chênh lệch độ cao hai cột đá liên tiếp được chọn, cộng cho tổng chi phí tháo dỡ các cột đá không được chọn.
Nói cách khác, gọi là dãy các vị trí được chọn, ta có công thức tính chi phí là:
Tìm cách chọn để cực tiểu hóa chi phí xây dựng cầu, đảm bảo cột đầu tiên và cuối cùng luôn được chọn.
Giới hạn:
- .
- .
¶ Quy hoạch động
Với kiến thức Quy hoạch động cơ bản, ta có thể xây dựng thuật toán với là chi phí xây dựng cầu nhỏ nhất, trong các phương án bắt đầu từ cột đầu tiên, và kết thúc ở cột thứ . Để tính , ta thử tất cả các vị trí là cột đá được chọn nằm ngay trước , sau đó cộng thêm và chi phí để tháo dỡ các cột đá từ vị trí đến . Công thức truy hồi như sau:
Thuật toán Quy hoạch động như trên sẽ có độ phức tạp là -- chưa đủ để giải quyết bài toán.
¶ Áp dụng Li-chao tree
Với công thức truy hồi , ta có thể biến đổi thành:
với .
Ta có thể nhóm biểu thức trên thành nhóm:
Nhóm thứ ba chỉ phụ thuộc vào nên nhiệm vụ còn lại là tìm để cực tiểu hóa nhóm đầu tiên. Có thể thấy, nhóm này có dạng phương trình đường thẳng với và .
Đến đây, ta định nghĩa phương trình đường thẳng . Như vậy, công thức truy hồi được biến đổi thành:
Ta đã đưa công thức truy hồi thành dạng bài quen thuộc của Li-chao tree: Để tính , ta tìm đường thẳng có giá trị bé nhất tại điểm cộng thêm