Li Chao Tree

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

huunguyen · Last updated 8, Tháng 4, 2026, 15:24

Li Chao Tree là cấu trúc dữ liệu hỗ trợ thêm đường thẳng và truy vấn giá trị nhỏ nhất tại một điểm $x$ tùy ý, trong $O (\log V)$ mỗi thao tác ( $V$ là khoảng giá trị $x$ ).

Đây là một biến thể của Convex Hull Trick nhưng hoạt động khi query không đơn điệu (CHT stack chỉ dùng được khi query đơn điệu).

Ứng dụng: DP optimization khi $a [i]$ (giá trị query) không đơn điệu, nhưng công thức chuyển vẫn có dạng $b [j] \cdot x + c [j]$ .

Ý tưởng

Xây dựng segment tree trên trục $x$ . Mỗi node $[l, r]$ lưu một đường thẳng "chiếm ưu thế" tại midpoint $m i d$ . Khi thêm đường thẳng mới, so sánh tại midpoint và đẩy đường thẳng "thua" xuống con tương ứng.

Bất biến: Tại node $[l, r]$ , đường thẳng được lưu là tốt nhất tại $m i d = (l + r) / 2$ trong số tất cả đường thẳng đã thêm vào node này và tổ tiên của nó.

Cài đặt — Đoạn cố định

const long long INF = 1e18;

struct Line {
    long long m, b;
    long long eval(long long x) const { return m * x + b; }
};

struct LiChaoTree {
    int lo, hi;
    vector<Line> tree;
    vector<bool> has;

    LiChaoTree(int lo, int hi) : lo(lo), hi(hi),
        tree(4*(hi-lo+1), {0, INF}), has(4*(hi-lo+1), false) {}

    void add(Line line, int node, int l, int r) {
        int mid = (l + r) / 2;
        bool left_better  = line.eval(l)   < tree[node].eval(l);
        bool mid_better   = line.eval(mid) < tree[node].eval(mid);

        if (mid_better) {
            swap(tree[node], line);
            has[node] = true;
        }

        if (l == r) return;

        if (left_better != mid_better)
            add(line, 2*node, l, mid);
        else
            add(line, 2*node+1, mid+1, r);
    }

    void add(long long m, long long b) {
        add({m, b}, 1, lo, hi);
    }

    long long query(int x, int node, int l, int r) {
        long long res = has[node] ? tree[node].eval(x) : INF;
        if (l == r) return res;
        int mid = (l + r) / 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));
    }

    long long query(int x) { return query(x, 1, lo, hi); }
};

// Sử dụng:
LiChaoTree lct(-1e9, 1e9);
lct.add(m, b);              // thêm đường y = m*x + b
long long ans = lct.query(x);   // min trên tất cả đường tại x

Cài đặt — Dynamic (tọa độ nén hoặc online)

Khi $x$ không biết trước hoặc khoảng quá lớn, dùng segment tree động (con trỏ):

struct Node {
    Line line;
    bool has;
    int left, right;
} nodes[MAXN * 40];
int cnt_nodes = 0;

int new_node() {
    nodes[cnt_nodes] = {{0, INF}, false, -1, -1};
    return cnt_nodes++;
}

So sánh với CHT stack

	CHT Stack	Li Chao Tree
Điều kiện	Query đơn điệu	Bất kỳ
Thời gian query	$O (1)$ amortized	$O (\log V)$
Thời gian insert	$O (1)$ amortized	$O (\log V)$
Cài đặt	Đơn giản	Trung bình

Ví dụ DP

// dp[i] = min_{j<i} (dp[j] + b[j]*a[i])
// Mỗi j thêm đường thẳng: slope=b[j], intercept=dp[j]
// Query tại x=a[i]

LiChaoTree lct(MIN_A, MAX_A);
dp[0] = 0;
lct.add(b[0], dp[0]);

for (int i = 1; i <= n; i++) {
    dp[i] = lct.query(a[i]);
    lct.add(b[i], dp[i]);
}

Khi nào dùng Li Chao Tree?

CHT optimization nhưng query không đơn điệu.
Bài toán geometry: tìm đường thẳng gần nhất tại một điểm.
Online CHT (thêm và query xen kẽ tùy ý).

Bình luận

Không có bình luận tại thời điểm này.