Wiki › Cấu trúc dữ liệu › Cây › Li Chao Tree

Li Chao Tree

huunguyen Updated Tháng sáu 2, 2026

Li Chao Tree là cấu trúc dữ liệu cho phép thêm đường thẳng $y = m \cdot x + b$ vào một tập, rồi truy vấn giá trị nhỏ nhất (hoặc lớn nhất) của tập các đường thẳng đó tại một điểm $x$ bất kỳ. Mỗi thao tác chạy trong $O (\log V)$ , với $V$ là số điểm $x$ phân biệt có thể hỏi.

Bài toán điển hình: ta có DP dạng

$d p [i] = {min}_{j < i} (m_{j} \cdot x_{i} + b_{j}),$

trong đó mỗi trạng thái $j$ sinh ra một đường thẳng có hệ số góc $m_{j}$ và tung độ gốc $b_{j}$ , còn truy vấn là tính giá trị nhỏ nhất của các đường thẳng tại $x = x_{i}$ . Nếu tính trực tiếp thì mất $O (N^{2})$ ; Li Chao Tree hạ xuống $O (N \log V)$ .

Đây là một lựa chọn thay cho Convex Hull Trick (CHT). Khác biệt then chốt: CHT dạng stack chỉ chạy được khi hệ số góc thêm vào đơn điệu và điểm truy vấn đơn điệu. Li Chao Tree không cần điều kiện đơn điệu nào — thêm đường với hệ số góc tùy ý, hỏi tại điểm tùy ý, xen kẽ thoải mái (online). Đổi lại mỗi thao tác là $O (\log V)$ thay vì $O (1)$ khấu hao.

Ý tưởng / Trực giác

Ta dựng một segment tree trên trục giá trị $x$ (không phải trên mảng dữ liệu). Mỗi node phụ trách một đoạn $[l, r]$ của trục $x$ và chỉ lưu đúng một đường thẳng.

Câu hỏi mấu chốt: với một node $[l, r]$ , ta nên giữ đường nào? Câu trả lời: giữ đường tốt nhất tại điểm giữa $m i d = ⌊ (l + r) / 2 ⌋$ trong số mọi đường từng "đi qua" node này.

Khi thêm một đường mới line vào node đang giữ đường cur, hãy nhìn vào hai điểm: điểm giữa $m i d$ và một đầu mút (chẳng hạn $l$ ). Hai đường thẳng cắt nhau tại tối đa một điểm, nên trên đoạn $[l, r]$ thứ tự "đường nào thấp hơn" chỉ đổi nhiều nhất một lần. Từ đó:

So tại $m i d$ : nếu line thấp hơn cur tại $m i d$ , đổi chỗ hai đường — bây giờ node giữ line, còn cur trở thành đường "thua" cần đẩy xuống.
So tại đầu mút $l$ : nếu đường thua tốt hơn ở phía $l$ (tức quan hệ tại $l$ và tại $m i d$ khác nhau), thì giao điểm nằm ở nửa trái → đẩy đường thua xuống con trái. Ngược lại đẩy xuống con phải.

Vì đường thua chỉ có thể "ngoi lên" trên đúng một nửa, ta luôn đẩy nó về đúng nửa chứa giao điểm, và đệ quy. Mỗi lần thêm đi xuống tối đa $\log V$ tầng.

Bất biến (invariant) sau khi thêm xong: tại mỗi node $[l, r]$ , đường được lưu là đường tốt nhất tại $m i d$ trong số tất cả đường đã thêm mà đường đi của chúng có ghé qua node này. Nhờ vậy, khi truy vấn tại $x$ , đáp án tối ưu chắc chắn nằm trên đường được lưu tại một node nào đó trên đường đi từ gốc xuống lá $x$ : ta chỉ cần lấy $min$ giá trị của các đường lưu dọc theo $O (\log V)$ node đó.

Vì sao chỉ cần xét dọc đường đi? Đường tối ưu tại $x$ , giả sử là $L^{\} *$ , khi được thêm vào đã được "đẩy" theo đúng quy tắc trên. Tại mỗi node nó đi qua, hoặc nó được giữ lại (nếu thắng tại $m i d$ ), hoặc nó bị đẩy xuống nửa chứa $x$ . Cứ thế nó hoặc dừng tại một node tổ tiên của $x$ , hoặc tiến mãi tới lá $x$ . Trong cả hai trường hợp, $L^{\} *$ có mặt trên đường gốc→lá của $x$ .

Ví dụ chạy tay

Xét trục $x \in [0, 3]$ và lần lượt thêm 3 đường (tìm min):

$A : y = 2 x + 0$
$B : y = - x + 3$
$C : y = 0 \cdot x + 1$

Giá trị tại các điểm $x = 0, 1, 2, 3$ :

$x$	$A = 2 x$	$B = - x + 3$	$C = 1$	min đúng
0	0	3	1	0 (A)
1	2	2	1	1 (C)
2	4	1	1	1 (B/C)
3	6	0	1	0 (B)

Cây dựng trên $[0, 3]$ , với $m i d$ của gốc là $⌊ (0 + 3) / 2 ⌋ = 1$ :

                node1 [0,3]  mid=1
                /              \
       node2 [0,1] mid=0     node3 [2,3] mid=2
        /     \               /      \
   [0,0]    [1,1]         [2,2]     [3,3]

Thêm A ( $2 x$ ): cây rỗng, gốc nhận luôn A. Gốc giữ A.

Thêm B ( $- x + 3$ ) tại gốc [0,3], mid=1:

Tại $m i d = 1$ : $B (1) = 2$ , $A (1) = 2$ — không nhỏ hơn hẳn, không đổi (gốc vẫn giữ A).
Tại đầu mút $l = 0$ : $B (0) = 3 > A (0) = 0$ → B không tốt hơn ở trái; quan hệ tại $l$ giống tại $m i d$ → đẩy B xuống con phải node3 [2,3].
Tại node3 [2,3], mid=2: node3 rỗng → nhận B. node3 giữ B.

Thêm C ( $1$ ) tại gốc [0,3], mid=1:

Tại $m i d = 1$ : $C (1) = 1 < A (1) = 2$ → đổi chỗ. Gốc giờ giữ C, đường thua là A ( $2 x$ ).
Tại $l = 0$ : đường thua $A (0) = 0$ so với đường đang giữ $C (0) = 1$ : A tốt hơn ở trái, mà tại $m i d$ thì A thua → giao điểm ở nửa trái → đẩy A xuống con trái node2 [0,1].
Tại node2 [0,1], mid=0: node2 rỗng → nhận A. node2 giữ A.

Trạng thái cuối:

        node1 [0,3]  giữ C: y=1
        /                 \
 node2 [0,1] giữ A:2x   node3 [2,3] giữ B:-x+3

Truy vấn $x = 0$ : đi gốc→trái→lá. Dọc đường: gốc giữ $C (0) = 1$ , node2 giữ $A (0) = 0$ . $min (1, 0) = 0$ . Đúng (A thắng tại 0). ✔

Truy vấn $x = 3$ : đi gốc→phải→lá. Dọc đường: gốc $C (3) = 1$ , node3 $B (3) = 0$ . $min (1, 0) = 0$ . Đúng (B thắng tại 3). ✔

Truy vấn $x = 1$ : dừng ở node2 (lá phía $[0, 1]$ ). Dọc đường: gốc $C (1) = 1$ , node2 $A (1) = 2$ . $min = 1$ . Đúng (C thắng tại 1). ✔

Cài đặt

Phiên bản đoạn cố định (đệ quy trên mảng tree), tìm min. Đường mặc định là đường "vô cực" ( $y = + \infty$ ) để node chưa có đường không ảnh hưởng kết quả.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 4e18;          // đủ lớn, vẫn an toàn long long

struct Line {
    ll m, b;                  // y = m*x + b
    ll eval(ll x) const { return m * x + b; }
};

struct LiChaoTree {
    ll lo, hi;                // miền giá trị x cho phép: [lo, hi]
    vector<Line> tree;        // mỗi node giữ 1 đường

    LiChaoTree(ll lo, ll hi) : lo(lo), hi(hi) {
        // 4*(số điểm) node là đủ cho cây phân đoạn trên [lo, hi]
        tree.assign(4 * (hi - lo + 1), {0, INF});
    }

    // thêm 'nw' vào cây con gốc 'node' phụ trách [l, r]
    void add(Line nw, int node, ll l, ll r) {
        ll mid = l + (r - l) / 2;           // tránh tràn khi l, r lớn
        // so sánh tại mid và tại biên trái l
        bool atMid  = nw.eval(mid) < tree[node].eval(mid);
        bool atLeft = nw.eval(l)   < tree[node].eval(l);

        // nếu thắng tại mid: giữ nw, đẩy đường cũ (đã swap vào nw) xuống
        if (atMid) swap(nw, tree[node]);

        if (l == r) return;                 // tới lá, dừng

        // giao điểm nằm ở nửa nào? => đẩy "đường thua" (nw) về đúng nửa đó
        if (atLeft != atMid) add(nw, 2*node,   l,     mid);
        else                 add(nw, 2*node+1, mid+1, r);
    }
    void add(ll m, ll b) { add({m, b}, 1, lo, hi); }

    // min trên đường đi gốc -> lá x
    ll query(ll x, int node, ll l, ll r) {
        ll res = tree[node].eval(x);
        if (l == r) return res;
        ll mid = l + (r - l) / 2;
        if (x <= mid) return min(res, query(x, 2*node,   l,     mid));
        else          return min(res, query(x, 2*node+1, mid+1, r));
    }
    ll query(ll x) { return query(x, 1, lo, hi); }
};

Cách dùng cho DP $d p [i] = {min}_{j < i} (b_{j} \cdot a_{i} + d p_{j})$ (mỗi $j$ là đường hệ số góc $b_{j}$ , tung độ gốc $d p_{j}$ ; query tại $x = a_{i}$ ):

LiChaoTree lct(MIN_A, MAX_A);
dp[0] = 0;
lct.add(b[0], dp[0]);                 // thêm đường của trạng thái 0
for (int i = 1; i <= n; i++) {
    dp[i] = lct.query(a[i]);          // min các đường tại x = a[i]
    lct.add(b[i], dp[i]);             // sinh đường mới từ dp[i]
}

Tìm max thay vì min? Cách gọn nhất: thêm đường $- m, - b$ và lấy $- query$ . Hoặc đảo mọi dấu < thành > và đổi INF thành -INF.

Độ phức tạp

Thời gian: mỗi lần add đi từ gốc xuống tối đa một lá, mỗi tầng làm $O (1)$ việc → $O (\log V)$ . Mỗi query cũng chỉ duyệt $O (\log V)$ node trên đường gốc→lá. Với $N$ thao tác: $O (N \log V)$ , trong đó $V = h i - l o + 1$ .
Bộ nhớ: phiên bản đoạn cố định cấp phát $4 V$ phần tử (mỗi phần tử là một Line) → $O (V)$ . Nếu $V$ tới $10^{9}$ thì $O (V)$ là quá lớn — khi đó phải nén tọa độ (rời rạc hóa $x$ về $O (N)$ giá trị) hoặc dùng Li Chao động (cấp phát node theo nhu cầu, $O (N \log V)$ bộ nhớ). Xem phần Mở rộng.

⚠️ Lỗi thường gặp

Tràn số khi tính m*x. Với $| m |, | x |$ cỡ $10^{9}$ , tích $m \cdot x$ tới $10^{18}$ — vượt int và sát trần long long. Luôn dùng long long (hoặc __int128 nếu còn cộng dồn). Triệu chứng: đáp án âm/loạn ngẫu nhiên. Đặc biệt cẩn thận với INF: nếu để INF = 1e18 rồi đường thật cộng vào, eval của đường ảo có thể tràn — dùng INF đủ lớn nhưng để dành biên (vd 4e18) và đảm bảo đường ảo không bao giờ tham gia phép cộng làm tràn; an toàn nhất là khởi tạo đường ảo bằng cờ "rỗng".
Tính mid bị tràn khi miền âm–dương lớn. (l + r) / 2 với $l = - 10^{9}, r = 10^{9}$ thì $l + r$ ổn, nhưng với miền lớn hơn dễ tràn. Dùng mid = l + (r - l) / 2. Ngoài ra mid phải tính theo đúng kiểu của $x$ (long long), không phải int.
Quên rằng cây dựng trên trục $x$ , không phải trên mảng. Số lá bằng số giá trị $x$ phân biệt, không bằng $N$ . Nếu $x$ nằm trong $[- 10^{9}, 10^{9}]$ mà bạn cấp phát $4 N$ node thì sai hoàn toàn. Phải hoặc nén tọa độ, hoặc dùng bản động với cận $[l o, h i]$ thật.
Truy vấn $x$ ngoài miền $[l o, h i]$ . Cây chỉ phủ $[l o, h i]$ ; hỏi ngoài miền cho kết quả rác. Đặt $l o, h i$ bao trùm mọi điểm sẽ hỏi (kể cả điểm tương lai nếu online).
Đẩy nhầm nửa. Việc chọn con trái/phải dựa trên so sánh tại $l$ và $m i d$ (atLeft != atMid). Nếu bạn so tại $r$ thay vì $l$ thì logic phải đổi tương ứng; trộn lẫn hai quy ước sẽ làm mất đường và ra kết quả lớn hơn thực tế (với min). Hãy nhất quán một quy ước.
Dùng Li Chao cho min nhưng quên đảo dấu khi cần max (hoặc ngược lại). Triệu chứng: đáp án ra giá trị "tốt ngược". Kiểm bằng một test nhỏ tự tính tay như ví dụ ở trên.

Biến thể / Mở rộng

Li Chao Tree động (dynamic). Khi miền $x$ rất rộng ( $10^{18}$ ) và không tiện nén tọa độ, dùng cây cấp phát node theo nhu cầu (con trỏ trái/phải tạo khi cần). Bộ nhớ $O (số thao tác \times \log V)$ . Phù hợp cho query online với tọa độ khổng lồ.

struct Node { Line line{0, INF}; Node *l = nullptr, *r = nullptr; };

void add(Node*& t, ll lo, ll hi, Line nw) {
    if (!t) { t = new Node{nw}; return; }
    ll mid = lo + (hi - lo) / 2;
    bool atMid  = nw.eval(mid) < t->line.eval(mid);
    bool atLeft = nw.eval(lo)  < t->line.eval(lo);
    if (atMid) swap(nw, t->line);
    if (lo == hi) return;
    if (atLeft != atMid) add(t->l, lo, mid, nw);
    else                 add(t->r, mid + 1, hi, nw);
}
ll query(Node* t, ll lo, ll hi, ll x) {
    if (!t) return INF;
    ll res = t->line.eval(x);
    if (lo == hi) return res;
    ll mid = lo + (hi - lo) / 2;
    if (x <= mid) return min(res, query(t->l, lo, mid, x));
    else          return min(res, query(t->r, mid + 1, hi, x));
}

Li Chao Tree merge / persistent. Có thể hợp nhất hai cây hoặc tạo bản bền vững để dùng trong DP trên cây (small-to-large, hoặc rút gọn theo cấu trúc cây con).
Kết hợp với Divide & Conquer Optimization / phân đoạn. Nhiều bài "chia $K$ đoạn, chi phí mỗi đoạn tuyến tính theo chỉ số" giải được bằng Li Chao theo từng lớp $k$ (mỗi lớp xây lại cây từ lớp trước), thay cho CHT khi điểm hỏi không đơn điệu.
So sánh nhanh với CHT:

	CHT (stack)	Li Chao Tree
Điều kiện hệ số góc	đơn điệu	bất kỳ
Điều kiện điểm hỏi	đơn điệu	bất kỳ
Thêm đường	$O (1)$ khấu hao	$O (\log V)$
Truy vấn	$O (1)$ / $O (\log)$	$O (\log V)$
Xóa đường	khó	(có bản nâng cao)
Cài đặt	đơn giản	trung bình

Bài tập luyện

Nhà kính của Sprout (greenhouse) — (Expert) Chia $N$ cây thành cụm phục vụ bởi $K$ nhà kính, tổng chi phí khoảng cách nhỏ nhất: DP $d p [k] [i]$ với công thức chuyển tuyến tính theo vị trí — đúng mẫu áp dụng CHT/Li Chao theo từng lớp $k$ .
Chuồng bò tròn mới (cbarnrev) — (Expert) Chia vòng tròn thành $K$ đoạn, chi phí mỗi đoạn là tổng "số bước × số bò" — hàm chuyển tuyến tính theo chỉ số đầu đoạn, tối ưu DP bằng kỹ thuật họ Li Chao/CHT.
Cải tạo vườn hoa (landscape) — (Expert) DP chuyển đất với chi phí phụ thuộc khoảng cách $| i - j |$ tuyến tính theo chỉ số; thuộc họ tối ưu hàm bậc nhất, luyện tư duy biến công thức chuyển thành "đường thẳng + truy vấn min".

(Ghi chú: pool CTOJ hiện rất ít bài gắn nhãn Li Chao/CHT; ba bài trên là các bài có công thức chuyển DP tuyến tính theo chỉ số — đúng họ kỹ thuật mà Li Chao Tree nhắm tới — sắp theo độ khó. Khi pool bổ sung thêm bài đúng tag, danh sách sẽ được cập nhật.)