Lý Siêu Thụ (Li Chao Tree) là một cấu trúc dữ liệu dựa trên cây phân đoạn, dùng để giải quyết các bài toán liên quan đến việc duy trì một tập hợp các hàm bậc nhất (đường thẳng hoặc đoạn thẳng) và hỗ trợ truy vấn giá trị lớn nhất (hoặc nhỏ nhất) tại một hoành độ cụ thể.

Nguyên lý cơ bản

Mỗi nút trong cây phân đoạn lưu trữ một "đường thẳng ưu thế" — đường thẳng có giá trị lớn nhất tại điểm giữa của đoạn mà nút đó quản lý. Khi chèn một đường thẳng mới, ta so sánh nó với đường thẳng hiện tại tại điểm giữa. Nếu đường mới tốt hơn, ta giữ lại đường mới ở nút hiện tại và đẩy đường cũ xuống một trong hai con tùy theo vị trí tương đối của chúng.

Truy vấn tại hoành độ x được thực hiện bằng cách đi từ gốc đến lá tương ứng với x, tính giá trị của tất cả các đường thẳng được lưu trên đường đi này và trả về giá trị lớn nhất.

Phiên bản mở rộng: hỗ trợ đoạn thẳng

Thay vì chèn toàn bộ đường thẳng, ta có thể chèn một đoạn thẳng xác định bởi hai đầu mút [l, r]. Khi đó, đoạn thẳng được phân rã thành các đoạn con phủ hoàn toàn các nút trong cây phân đoạn, và tại mỗi nút như vậy, ta thực hiện thao tác chèn như ở phiên bản cơ bản.

Dưới đây là mã giả cho thao tác chèn đoạn thẳng:

void update(int segL, int segR, int l, int r, Line newLine, int &node) {
    if (!node) node = ++nodeCount;
    if (l <= segL && segR <= r) {
        insertLine(segL, segR, newLine, node);
        return;
    }
    int mid = (segL + segR) / 2;
    if (l <= mid) update(segL, mid, l, r, newLine, left[node]);
    if (r > mid) update(mid + 1, segR, l, r, newLine, right[node]);
}

Hàm insertLine xử lý việc so sánh và hoán đổi giữa đường thẳng mới và đường thẳng hiện tại dựa trên giá trị tại điểm giữa.

Ứng dụng nâng cao: kết hợp với HLD và rời rạc hóa

Trong một số bài toán như P4069 [SDOI2016] Game, các đoạn thẳng không còn được định nghĩa trên miền liên tục mà trên các đoạn rời rạc (ví dụ: chỉ số DFS sau khi Heavy-Light Decomposition). Khi đó, Lý Siêu Thụ cần được xây dựng trên mảng đã rời rạc hóa.

Điểm khác biệt quan trọng: khi truy vấn một đoạn [ql, qr], không chỉ xét các nút phủ hoàn toàn đoạn đó, mà còn phải kiểm tra giá trị tại các đầu mút giao nhau giữa đoạn truy vấn và đoạn do nút quản lý, vì đoạn thẳng lưu trong nút có thể không phủ toàn bộ đoạn truy vấn.

Ví dụ khi tính giá trị nhỏ nhất trong đoạn [l, r] tại nút quản lý đoạn [L, R]:

if (hasLine[node]) {
    int x1 = max(l, L), x2 = min(r, R);
    res = min(res, eval(line[node], x1));
    res = min(res, eval(line[node], x2));
}

Việc bỏ qua bước này dẫn đến sai số dù rất nhỏ nhưng đủ gây WA.

Mẫu cài đặt gọn nhẹ

Dưới đây là một phiên bản tối giản của Lý Siêu Thụ hỗ trợ truy vấn giá trị lớn nhất tại một điểm:

namespace LiChao {
    const int INF = 1e18;
    struct Line { long long k, b; };
    vector<Line> tree;
    vector<bool> hasLine;
    int N;

    long long f(const Line& L, long long x) {
        return L.k * x + L.b;
    }

    void init(int size) {
        N = size;
        tree.assign(4 * N, {0, -INF});
        hasLine.assign(4 * N, false);
    }

    void addLine(Line nw, int v = 1, int l = 0, int r = -1) {
        if (r == -1) r = N - 1;
        if (!hasLine[v]) {
            hasLine[v] = true;
            tree[v] = nw;
            return;
        }
        int m = (l + r) / 2;
        bool leftBetter = f(nw, l) > f(tree[v], l);
        bool midBetter = f(nw, m) > f(tree[v], m);

        if (midBetter) swap(tree[v], nw);
        if (l == r) return;
        if (leftBetter != midBetter)
            addLine(nw, 2*v, l, m);
        else
            addLine(nw, 2*v+1, m+1, r);
    }

    long long query(int x, int v = 1, int l = 0, int r = -1) {
        if (r == -1) r = N - 1;
        long long res = hasLine[v] ? f(tree[v], x) : -INF;
        if (l == r) return res;
        int m = (l + r) / 2;
        if (x <= m) res = max(res, query(x, 2*v, l, m));
        else res = max(res, query(x, 2*v+1, m+1, r));
        return res;
    }
}