Li Chao Tree là gì ?

Xin chào các bạn, nếu như ở bài viết trước ta đã cùng nhau tìm hiểu về Cây Đoạn ( Segment Tree) là gì ?, trong bài viết này ta sẽ cùng nhau tìm hiểu về 1 biến thể của nó Li Chao Segment Tree và những ứng dụng của nó để giải quyết các bài toán phức tạp một cách nhanh chóng ...

Giới Thiệu

Li Chao Segment Tree (hay còn gọi là Lee Chao Tree) là một cấu trúc dữ liệu được thiết kế để giải quyết một tập hợp các bài toán liên quan đến một tập hàm tuyến tính (linear function), chẳng hạn như các đường thẳng có dạng $y = ax + b$. Cấu trúc này đặc biệt hữu ích khi các hàm này có một tính chất đặc biệt được gọi là tính chất siêu việt.

Tính chất siêu việt có thể được mô tả như sau:

Với hai hàm $f(x)$ và $g(x)$ cùng loại, nếu $f(t) $lớn hơn hoặc nhỏ hơn $g(t)$ tại một điểm $x=t$ nào đó, thì $f(x)$ sẽ tiếp tục lớn hơn hoặc nhỏ hơn $g(x)$ với tất cả $x > t$. Nói cách khác, một khi $f(x)$ "thắng" hoặc "thua" $g(x)$ tại một điểm nhất định, nó sẽ tiếp tục "thắng" hoặc "thua" với tất cả các điểm sau đó.

Mục tiêu:

• Mỗi nút của cây tương ứng với một đoạn và lưu trữ một đường thẳng $val$.
• Đảm bảo rằng mỗi truy vấn tại một điểm x bất kỳ, sẽ trả về giá trị nhỏ nhất (hoặc lớn nhất) của tất cả các đường thẳng $f1(x), f2(x),…, fn(x)$ tại điểm đó.

Cấu Trúc

Li Chao Tree, hay còn được gọi là Li Chao Segment Tree, là một cấu trúc dữ liệu dạng cây dùng để quản lý các đoạn thẳng (hàm tuyến tính) và tìm kiếm đoạn thẳng có cực đại hoặc cực tiểu trên một khoảng chỉ với độ phức tạp O(n log N).

• Cấu trúc của cây Li Chao là cây phân đoạn, cấu trúc dữ liệu cây nhị phân cân bằng. Cây được cân bằng để đảm bảo rằng mỗi nút lá có độ sâu gần như nhau, cho phép độ phức tạp thời gian logarit đối với các hoạt động như chèn và xóa.

Trên mỗi nút của cây phân đoạn, nó lưu trữ các hàm có giá trị lớn nhất (hoặc nhỏ nhất) tại điểm giữa của khoảng cho trước $[L, R)$. Mỗi nút lá đại diện cho một điểm duy nhất.

Cài đặt

Ở đây mình sử dụng hàm tuyến tính để cài đặt ví dụ,

struct line { int a, b; line(int _a, int _b): a(_a), b(_b) {} int f(int x) { return a * x + b; }
};

Trên mỗi nút của cây Segment Tree, chúng ta lưu trữ đường thẳng có giá trị lớn nhất (hoặc nhỏ nhất) tại điểm giữa. Cụ thể, nếu miền giá trị của nút là $[L, R)$, thì đường thẳng được lưu trữ trên nút đó sẽ có giá trị lớn nhất hoặc nhỏ nhất tại $(L + R) / 2$.

Chèn ( Insert )

Giả sử một đoạn $[l, r)$ đã lưu trữ đường $α$ (màu đỏ), và chúng ta thêm một đường $β$ (màu xanh), sẽ có bốn trường hợp xảy ra:

1. $f_{\alpha}(\text{mid}) < f_{\beta}(\text{mid}) \wedge m_{\alpha} > m_{\beta}$

Giá trị của đường $α$ (màu đỏ) nhỏ hơn giá trị của đường $β$ (màu xanh) tại $mid$. Nên đưa đường thẳng gốc (đường α) vào cây con và cập nhật.

2. $f_{\alpha}(\text{mid}) < f_{\beta}(\text{mid}) \wedge m_{\alpha} < m_{\beta}$

Cũng giống như trường hợp thứ nhất, giá trị của đường $α$ (màu đỏ) nhỏ hơn giá trị của đường $β$ (màu xanh) tại $mid$. Nên đưa đường thẳng gốc (đường $α$) vào cây con và cập nhật.

3. $f_{\alpha}(\text{mid}) > f_{\beta}(\text{mid}) \wedge m_{\alpha} > m_{\beta}$

Giá trị của đường $α$ (màu đỏ) lớn hơn (tối ưu hơn) giá trị của đường $β$ (màu xanh) tại $mid$. Nên đưa đường thẳng gốc (đường $α$) vào cây con và cập nhật.

4. $f_{\alpha}(\text{mid}) > f_{\beta}(\text{mid}) \wedge m_{\alpha} < m_{\beta}$

Đường thẳng gốc tại $mid$ vẫn tối ưu hơn. Đưa đường thẳng mới vào cây con và cập nhật.

Tổng kết các bước xử lý chèn:

• Tại mỗi nút của cây, nếu đường thẳng mới có giá trị tốt hơn (nhỏ hơn hoặc lớn hơn, tùy theo yêu cầu bài toán) tại điểm giữa đoạn [L, R) ta sẽ cập nhật nút đó bằng đường thẳng mới.
• Nếu đường thẳng cũ (hoặc mới) vẫn có thể tốt hơn trong một phần của đoạn, ta sẽ tiếp tục kiểm tra nó trong cây con tương ứng. Nếu giá trị tại điểm đầu của đoạn lớn hơn, ta sẽ đệ quy vào cây con bên trái; ngược lại, ta đệ quy vào cây con bên phải.
• Nếu đường thẳng mới hoàn toàn tốt hơn (hoặc kém hơn) đường thẳng cũ tại điểm giữa và tại cả hai điểm đầu và cuối của đoạn, ta không cần tiếp tục đệ quy nữa và có thể dừng lại.

Cài đặt với C++ Code:

struct Line { int a, b; Line(int _a, int _b) : a(_a), b(_b) {} // Hàm tính giá trị y = ax + b tại điểm x int f(int x) const { return a * x + b; }
}; struct SegTree { int l, r, mid; Line val = Line(0, 1e18); SegTree* ch[2] = {nullptr, nullptr}; // Hàm khởi tạo cho đoạn [l, r) SegTree(int _l, int _r) : l(_l), r(_r) { mid = (l + r) / 2; if (l == r - 1) return; // Nếu là nút lá, không cần phân nhánh thêm ch[0] = new SegTree(l, mid); // Tạo cây con bên trái ch[1] = new SegTree(mid, r); // Tạo cây con bên phải } // Hàm chèn một đường thẳng mới vào cây void insert(Line k) { // Đổi chỗ nếu đường mới tốt hơn tại điểm giữa if (k.f(mid) < val.f(mid)) std::swap(k, val); if (l == r - 1) return; // Nếu là nút lá, dừng lại // Đệ quy vào cây con bên trái hoặc bên phải dựa trên hệ số a if (k.a > val.a) { ch[0]->insert(k); } else { ch[1]->insert(k); } }
};

Truy vấn ( Query )

Khi truy vấn, ta thực hiện việc duyệt qua tất cả các đường thẳng được lưu trữ trong các nút của cây đoạn. Tại mỗi nút, ta lấy giá trị của đường thẳng tại điểm x đang truy vấn và tìm giá trị nhỏ nhất (hoặc lớn nhất) trong số các giá trị đó. Giá trị tại điểm giữa ($mid$) của đoạn được chọn làm giá trị đại diện cho đoạn đó.

Cài đặt với C++ Code:

// Hàm truy vấn giá trị tại điểm x
int query(int x) const { if (l == r - 1) { return val.f(x); // Nếu là nút lá, trả về giá trị tại x } // Truy vấn đệ quy vào cây con bên trái hoặc bên phải và lấy giá trị nhỏ nhất if (x < mid) { return std::min(val.f(x), ch[0]->query(x)); } else { return std::min(val.f(x), ch[1]->query(x)); }
}

Ứng dụng

1. Bài Toán Đường Cong Lồi (Convex Hull Trick)

Mô tả

Cho một dãy các hàm tuyến tính $y = ax+b$ và một tập hợp các điểm $x$. Yêu cầu tìm giá trị nhỏ nhất của tất cả các hàm tuyến tính tại mỗi điểm $x$.

Giải pháp

Sử dụng Li Chao Tree để duy trì và truy vấn các hàm tuyến tính

Lời giải tham khảo

#include <iostream>
#include <vector>
#include <limits> using namespace std; struct Line { int a, b; Line(int _a, int _b) : a(_a), b(_b) {} // Hàm tính giá trị y = ax + b tại điểm x int f(int x) const { return a * x + b; }
}; struct SegTree { int l, r, mid; Line val = Line(0, 1e9); // Giá trị khởi tạo lớn để đảm bảo không ảnh hưởng kết quả SegTree* ch[2] = {nullptr, nullptr}; // Hàm khởi tạo cho đoạn [l, r) SegTree(int _l, int _r) : l(_l), r(_r) { mid = (l + r) / 2; if (l == r - 1) return; // Nếu là nút lá, không cần phân nhánh thêm ch[0] = new SegTree(l, mid); // Tạo cây con bên trái ch[1] = new SegTree(mid, r); // Tạo cây con bên phải } // Hàm chèn một đường thẳng mới vào cây void insert(Line k) { // Đổi chỗ nếu đường mới tốt hơn tại điểm giữa if (k.f(mid) < val.f(mid)) std::swap(k, val); if (l == r - 1) return; // Nếu là nút lá, dừng lại // Đệ quy vào cây con bên trái hoặc bên phải dựa trên hệ số a if (k.a > val.a) { ch[0]->insert(k); } else { ch[1]->insert(k); } } // Hàm truy vấn giá trị tại điểm x int query(int x) const { if (l == r - 1) { return val.f(x); // Nếu là nút lá, trả về giá trị tại x } // Truy vấn đệ quy vào cây con bên trái hoặc bên phải và lấy giá trị nhỏ nhất if (x < mid) { return std::min(val.f(x), ch[0]->query(x)); } else { return std::min(val.f(x), ch[1]->query(x)); } }
}; int main() { int n = 10; // Giả sử n là phạm vi của các giá trị x SegTree st(0, n); // Thêm một số hàm tuyến tính st.insert(Line(2, 3)); // y = 2x + 3 st.insert(Line(-1, 4)); // y = -1x + 4 // Truy vấn giá trị nhỏ nhất tại x = 5 cout << "Min value at x = 5: " << st.query(5) << endl; return 0;
}

2. (Coming soon)

Áp dụng

Dưới đây sẽ là một số bài toán hay (theo góc nhìn của người viết và các tác giả trong phần tham khảo) và lời giải dễ hiểu sử dụng cấu trúc dữ liệu Li Chao Tree.

atcoder - Shopping in AtCoder store

Giải pháp

Khi đọc xong đề bài, bạn có thể nhận thấy rằng khi chúng ta điều chỉnh giá của mặt hàng thứ $j$, trước tiên sắp xếp $B$ theo thứ tự giảm dần. Nếu muốn làm cho $i$ người mua hàng, thì giá lớn nhất $P_j = B_i + C_j$. Tổng lợi nhuận là $i \times (B_i + C_j)$, sau đó sắp xếp lại thành $iC_j + iB_i$. Nhưng việc liệt kê $i = [1, n]$ sẽ dẫn đến TLE, vì vậy chúng ta có thể chèn vào $n$ đoạn thẳng $f_i(x) = ix + iB_i$. Sau đó, chỉ cần cho giá trị $C_j$ đã cho, tìm $\max_{\forall i \in [1,n]} iC_j + iB_i$ là được.

Lời giải tham khảo

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
struct line{ int a, b; line(int _a, int _b):a(_a),b(_b){} int f(int x){ return a*x+b; }
};
struct seg{ int l, r, mid; line val = line(0, 0); seg *lc = NULL, *rc = NULL; seg(int _l, int _r):l(_l),r(_r),mid((_l+_r)>>1){} void newNode(){ if(lc != nullptr || l == r-1)return; lc = new seg(l, mid); rc = new seg(mid, r); } void insert(line k){ if(k.f(mid) < val.f(mid)) swap(k, val); if(l == r-1)return; newNode(); if(k.a > val.a) rc->insert(k); else lc->insert(k); } int query(int idx){ if(l == r-1 || lc == nullptr) return val.f(idx); int ans = val.f(idx); if(idx < mid) ans = max(ans, lc->query(idx)); else ans = max(ans, rc->query(idx)); return ans; }
};
signed main(){ int n, m; cin >> n >> m; vector<int> b(n), c(m); seg sg(0, 1e9); for(int i = 0; i < n; i++) cin >> b[i]; for(int i = 0; i < m; i++) cin >> c[i]; sort(all(c)); sort(all(b)); reverse(all(b)); for(int i = 1; i <= n; i++) sg.insert(line(i, (i-1)*b[i-1])); for(int i = 0; i < m; i++) cout << sg.query(c[i]) << " "; cout << endl;
}

Bài Tập

comming soon...

Tham khảo

Bài viết này là kết quả của sự tổng hợp và nghiên cứu kiến thức về Li Chao Tree, xin trân trọng cảm ơn các tác giả và các kiến thức từ các bài viết của họ đã giúp tôi có thể hoàn thành bài viết này

1. Bài viết "Convex hull trick and Li Chao tree" tại cp-algorithms.com
2. Bài viết introduction to Li Chao Tree tại geeksforgeeks.org
3. Blog của robert1003 về Li Chao Tree
4. Bài viết tại Oi Wiki Tiếng trung về Li Chao Tree
5. Bài viết về Segment tree của người dùng @soondro2266 tại HackMD và nhiều hơn thế nữa ...