Li Chao Tree

Chèn và hỏi

Mỗi nút phụ trách đoạn $[l, r]$ của miền $x$ và giữ một đường. Chèn đường $f$ vào nút đang giữ $g$:

1. So $f$ và $g$ tại điểm giữa $m$; đường nhỏ hơn ở $m$ ở lại nút, đường kia đi tiếp.
2. Hai đường cắt nhau tối đa một lần, nên đường thua ở $m$ chỉ có thể thắng ở một nửa: nửa trái nếu nó thắng ở $l$, ngược lại nửa phải. Đệ quy vào đúng nửa đó.

Nút rỗng thì đặt đường vào và dừng, nên mỗi lần chèn tạo tối đa một nút mới: cây động trên miền $[-10^9, 10^9]$ chỉ cần số nút bằng số đường. Hỏi tại $x$: đi từ gốc xuống lá chứa $x$, lấy nhỏ nhất của các đường gặp trên đường đi. Đúng vì đường tốt nhất tại $x$ luôn nằm trên đường từ gốc tới lá đó.

Điểm giữa của đoạn có số âm lấy bằng (l + r) >> 1 để làm tròn xuống. Giá trị $ax + b$ với $|a|, |x| \le 10^9$, $|b| \le 10^{18}$ vừa long long.

Ví dụGiá Trị Thấp Nhất

Đề. Có sẵn $n$ đường, rồi $q$ thao tác (tổng tới $4 \cdot 10^5$): thêm đường $ax + b$, hoặc hỏi giá trị nhỏ nhất tại $x$, với $|a|, |x| \le 10^9$, $|b| \le 10^{18}$.

Lời giải. Cây Li Chao trên miền $x \in [-10^9, 10^9]$, nút chỉ được tạo khi cần, nên số nút không vượt số đường. Đường có sẵn và đường thêm sau đều chèn cùng một cách; hỏi là đi một đường từ gốc xuống.

Bước 1: chèn một đường. Mỗi nút giữ một đường; lc, rc bằng 0 là chưa có con. insert nhận x theo tham chiếu nên tạo nút mới là gán thẳng vào ô con của cha. left là đường mới tốt hơn ở đầu trái $l$, mid là tốt hơn ở trung điểm $m$. Nếu mid thì đổi chỗ: nút luôn giữ đường tốt hơn tại $m$, đường thua đi tiếp.

void insert(int &x, ll l, ll r, ll a, ll b) {
    if (!x) {
        x = ++tot, la[x] = a, lb[x] = b;
        return;
    }
    ll m = (l + r) >> 1;
    bool left = a * l + b < f(x, l), mid = a * m + b < f(x, m);
    if (mid) swap(la[x], a), swap(lb[x], b);
    if (l == r) return;
    if (left != mid) insert(lc[x], l, m, a, b);
    else insert(rc[x], m + 1, r, a, b);
}

Đi nửa nào: hai đường cắt nhau tối đa một lần. left != mid thì hai đường đổi thứ tự giữa $l$ và $m$, nên đường thua chỉ có thể thắng ở nửa trái. left == mid thì trên cả nửa trái đường giữ ở nút vẫn tốt hơn, đường thua chỉ còn cơ hội ở nửa phải.

Bước 2: hỏi. Đi từ gốc xuống theo $p$, lấy nhỏ nhất của mọi đường gặp. Đường tốt nhất tại $p$ hoặc nằm ở một nút trên đường đi, hoặc đã bị đẩy xuống đúng nửa chứa $p$.

while (x) {
    res = min(res, f(x, p));
    ll m = (l + r) >> 1;
    if (p <= m) x = lc[x], r = m;
    else x = rc[x], l = m + 1;
}

Tràn số: $|a \cdot p| \le 10^{18}$ cộng $|b| \le 10^{18}$ vẫn dưới $9{,}2 \cdot 10^{18}$. (l + r) >> 1 làm tròn xuống cả khi $l + r$ âm, khác với / 2.

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

const int M = 4e5 + 5;
const ll L = -1e9, R = 1e9, INF = LLONG_MAX;
int tot, root, lc[M], rc[M];
ll la[M], lb[M];

ll f(int x, ll p) {
    return la[x] * p + lb[x];
}

void insert(int &x, ll l, ll r, ll a, ll b) {
    if (!x) {
        x = ++tot, la[x] = a, lb[x] = b;
        return;
    }
    ll m = (l + r) >> 1;
    bool left = a * l + b < f(x, l), mid = a * m + b < f(x, m);
    if (mid) swap(la[x], a), swap(lb[x], b);
    if (l == r) return;
    if (left != mid) insert(lc[x], l, m, a, b);
    else insert(rc[x], m + 1, r, a, b);
}

ll query(ll p) {
    ll res = INF, l = L, r = R;
    int x = root;
    while (x) {
        res = min(res, f(x, p));
        ll m = (l + r) >> 1;
        if (p <= m) x = lc[x], r = m;
        else x = rc[x], l = m + 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        insert(root, L, R, a, b);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 0) {
            ll a, b;
            cin >> a >> b;
            insert(root, L, R, a, b);
        } else {
            ll x;
            cin >> x;
            cout << query(x) << '\n';
        }
    }
}

ChạyInput2 5
2 5
-1 8
1 0
0 1 -3
1 4
1 -2
1 3

Output5
1
-5
0

Mỗi thao tác $O(\log 2 \cdot 10^9) \approx 31$ bước.

Đoạn thẳng

Đường chỉ có hiệu lực trên $[l, r)$: đi xuống cây phân đoạn như cập nhật đoạn, tại mỗi nút nằm trọn trong $[l, r)$ thì chèn kiểu Li Chao bình thường trong cây con của nút đó. Có $O(\log C)$ nút phủ, mỗi nút chèn tốn $O(\log C)$, tổng $O(\log^2 C)$ mỗi đoạn; hỏi vẫn $O(\log C)$.

Làm ngoại tuyến thì nén các điểm hỏi thành mảng xs đã sắp, dựng cây Li Chao tĩnh trên chỉ số $0..k-1$, so sánh đường tại xs[m]. Đoạn $[l, r)$ đổi thành khoảng chỉ số các điểm hỏi nằm trong nó. Không có điểm hỏi nào trong đoạn thì bỏ qua đường đó.

Ví dụHàm Trên Nửa Khoảng

Đề. $n + q \le 4 \cdot 10^5$ thao tác: thêm hàm $ax + b$ hiệu lực trên $[l, r)$, hoặc hỏi giá trị nhỏ nhất tại $x$ (in INFINITY nếu không có hàm nào).

Lời giải. Làm ngoại tuyến. Đọc hết thao tác, gom mọi $x$ được hỏi, sắp và bỏ trùng thành xs. Cây Li Chao dựng trên chỉ số $0..k-1$, so sánh các đường tại xs[m] thay vì tại $m$. Hàm hiệu lực trên $[l, r)$ đổi thành khoảng chỉ số các điểm hỏi nằm trong đó; khoảng này phủ bởi $O(\log k)$ nút của cây phân đoạn, và mỗi nút phủ nhận một lần chèn Li Chao trong cây con của nó.

Bước 1: chèn Li Chao trên chỉ số. Giống insert của ví dụ trước, viết bằng vòng lặp, thay $l$, $m$ bằng xs[l], xs[m]. has[x] = 0 là nút chưa có đường.

bool left = a * xs[l] + b < la[x] * xs[l] + lb[x];
bool mid = a * xs[m] + b < la[x] * xs[m] + lb[x];
if (mid) swap(la[x], a), swap(lb[x], b);
if (l == r) return;
if (left != mid) x = 2 * x, r = m;
else x = 2 * x + 1, l = m + 1;

Bước 2: chèn theo đoạn. Đi như cập nhật đoạn của cây phân đoạn; ở mỗi nút nằm trọn trong khoảng thì gọi push cho cây con của nút đó. Đường đặt ở nút này chỉ được hỏi bởi các điểm nằm trong đoạn của nút, nên nó không lọt ra ngoài $[l, r)$.

void addSeg(int x, int l, int r, int ql, int qr, ll a, ll b) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        push(x, l, r, a, b);
        return;
    }
    int m = (l + r) / 2;
    addSeg(2 * x, l, m, ql, qr, a, b);
    addSeg(2 * x + 1, m + 1, r, ql, qr, a, b);
}

Bước 3: đổi $[l, r)$ thành chỉ số. ql là điểm hỏi đầu tiên $\ge l$, qr là điểm hỏi cuối cùng $< r$. ql > qr nghĩa là không ai hỏi trong khoảng đó, bỏ qua đường. Thao tác làm lại đúng thứ tự đọc, nên câu hỏi chỉ thấy các hàm thêm trước nó.

int ql = lower_bound(xs.begin(), xs.end(), o[1]) - xs.begin();
int qr = lower_bound(xs.begin(), xs.end(), o[2]) - xs.begin() - 1;
if (ql <= qr) addSeg(1, 0, k - 1, ql, qr, o[3], o[4]);

query đi từ gốc tới lá p; mỗi nút trên đường đi chứa p trong đoạn của mình, nên mọi đường ở đó đều có hiệu lực tại xs[p].

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

const int N = 2e5 + 5;
const ll INF = LLONG_MAX;
int k, has[4 * N];
ll la[4 * N], lb[4 * N];
vector<ll> xs;

void push(int x, int l, int r, ll a, ll b) {
    while (true) {
        if (!has[x]) {
            has[x] = 1, la[x] = a, lb[x] = b;
            return;
        }
        int m = (l + r) / 2;
        bool left = a * xs[l] + b < la[x] * xs[l] + lb[x];
        bool mid = a * xs[m] + b < la[x] * xs[m] + lb[x];
        if (mid) swap(la[x], a), swap(lb[x], b);
        if (l == r) return;
        if (left != mid) x = 2 * x, r = m;
        else x = 2 * x + 1, l = m + 1;
    }
}

void addSeg(int x, int l, int r, int ql, int qr, ll a, ll b) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        push(x, l, r, a, b);
        return;
    }
    int m = (l + r) / 2;
    addSeg(2 * x, l, m, ql, qr, a, b);
    addSeg(2 * x + 1, m + 1, r, ql, qr, a, b);
}

ll query(int p) {
    ll res = INF;
    int x = 1, l = 0, r = k - 1;
    while (true) {
        if (has[x]) res = min(res, la[x] * xs[p] + lb[x]);
        if (l == r) return res;
        int m = (l + r) / 2;
        if (p <= m) x = 2 * x, r = m;
        else x = 2 * x + 1, l = m + 1;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    vector<array<ll, 5>> ops;
    for (int i = 0; i < n; i++) {
        ll l, r, a, b;
        cin >> l >> r >> a >> b;
        ops.push_back({0, l, r, a, b});
    }
    for (int i = 0; i < q; i++) {
        ll t;
        cin >> t;
        if (t == 0) {
            ll l, r, a, b;
            cin >> l >> r >> a >> b;
            ops.push_back({0, l, r, a, b});
        } else {
            ll x;
            cin >> x;
            ops.push_back({1, x, 0, 0, 0});
            xs.push_back(x);
        }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    k = xs.size();
    for (array<ll, 5> o : ops) {
        if (o[0] == 0) {
            int ql = lower_bound(xs.begin(), xs.end(), o[1]) - xs.begin();
            int qr = lower_bound(xs.begin(), xs.end(), o[2]) - xs.begin() - 1;
            if (ql <= qr) addSeg(1, 0, k - 1, ql, qr, o[3], o[4]);
        } else {
            ll v = query(lower_bound(xs.begin(), xs.end(), o[1]) - xs.begin());
            if (v == INF) cout << "INFINITY\n";
            else cout << v << '\n';
        }
    }
}

ChạyInput1 5
0 5 2 3
1 0
1 5
0 4 8 -1 10
1 4
1 6

Output3
INFINITY
6
4

Mỗi hàm $O(\log^2 k)$, mỗi câu hỏi $O(\log k)$.

DP với hàm bậc nhất

DP dạng $dp_i = \min_{j < i} \big(dp_j + g(j) \cdot x_i + h(j)\big) + c(i)$: với mỗi $j$ đã tính xong, thêm đường hệ số góc $g(j)$, tung độ gốc $dp_j + h(j)$; tính $dp_i$ là hỏi tại $x_i$. Bình phương hiệu là dạng hay gặp: $(h_i - h_j)^2 = h_i^2 - 2 h_i h_j + h_j^2$, phần chỉ phụ thuộc $i$ đưa ra ngoài, phần chỉ phụ thuộc $j$ vào tung độ gốc, tích chéo $-2 h_j \cdot h_i$ là hệ số góc nhân điểm hỏi.

Khi điểm hỏi nguyên trong miền nhỏ (như $h \le 10^6$), dùng cây tĩnh trên mảng $4C$ phần tử, không cần nút động.

Ví dụBệ Cao Dần

Đề. $n \le 2 \cdot 10^5$ bệ, độ cao tăng $h_i \le 10^6$. Nhảy từ $i$ tới $j > i$ tốn $(h_j - h_i)^2 + C$, $C \le 10^{12}$. Tìm chi phí nhỏ nhất từ bệ 1 tới bệ $n$.

Lời giải. $dp_i$ là chi phí nhỏ nhất để tới bệ $i$. Khai triển $(h_i - h_j)^2$ được

Phần trong ngoặc là giá trị tại $x = h_i$ của đường hệ số góc $-2h_j$, tung độ $dp_j + h_j^2$. Tính xong $dp_j$ thì thêm đường của $j$; tính $dp_i$ là hỏi nhỏ nhất tại $h_i$. Độ cao nguyên tới $10^6$ nên dùng cây Li Chao tĩnh trên mảng $4 \cdot 10^6$ ô, nút $x$ có con $2x$, $2x + 1$; insert, query viết bằng vòng lặp như các ví dụ trước.

Bệ đầu có $dp_0 = 0$, thêm đường của nó trước vòng lặp. Mỗi bệ sau: hỏi tại $h_i$, cộng $h_i^2 + C$, rồi thêm đường của chính nó.

insert(-2 * h[0], h[0] * h[0]);
for (int i = 1; i < n; i++) {
    dp[i] = query(h[i]) + h[i] * h[i] + c;
    insert(-2 * h[i], dp[i] + h[i] * h[i]);
}

Độ lớn: hệ số góc tới $2 \cdot 10^6$ nhân $x$ tới $10^6$ là $2 \cdot 10^{12}$; $dp$ không quá $n (C + 10^{12})$, khoảng $4 \cdot 10^{17}$, vẫn vừa long long.

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

const int X = 1e6;
const ll INF = LLONG_MAX;
ll la[4 * X + 5], lb[4 * X + 5];
bool has[4 * X + 5];

void insert(ll a, ll b) {
    int x = 1, l = 1, r = X;
    while (true) {
        if (!has[x]) {
            has[x] = 1, la[x] = a, lb[x] = b;
            return;
        }
        int m = (l + r) / 2;
        bool left = a * l + b < la[x] * l + lb[x], mid = a * m + b < la[x] * m + lb[x];
        if (mid) swap(la[x], a), swap(lb[x], b);
        if (l == r) return;
        if (left != mid) x = 2 * x, r = m;
        else x = 2 * x + 1, l = m + 1;
    }
}

ll query(ll p) {
    ll res = INF;
    int x = 1, l = 1, r = X;
    while (true) {
        if (has[x]) res = min(res, la[x] * p + lb[x]);
        if (l == r) return res;
        int m = (l + r) / 2;
        if (p <= m) x = 2 * x, r = m;
        else x = 2 * x + 1, l = m + 1;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    ll c;
    cin >> n >> c;
    vector<ll> h(n), dp(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    dp[0] = 0;
    insert(-2 * h[0], h[0] * h[0]);
    for (int i = 1; i < n; i++) {
        dp[i] = query(h[i]) + h[i] * h[i] + c;
        insert(-2 * h[i], dp[i] + h[i] * h[i]);
    }
    cout << dp[n - 1] << '\n';
}

ChạyInput6 7
2 5 6 11 12 20

Output134

$O(n \log 10^6)$.

Gộp cây Li Chao trên cây

DP trên cây $dp_u = \min_{v \in \text{subtree}(u),\, v \ne u} (a_u \cdot b_v + dp_v)$: mỗi đỉnh $v$ đóng góp đường $b_v x + dp_v$, đỉnh $u$ hỏi tại $a_u$ trên tập đường của cây con. Mỗi đỉnh giữ một cây Li Chao động; cây của $u$ là gộp cây của các con: merge(x, y) chèn đường ở gốc $y$ vào $x$ rồi gộp đệ quy các cặp con trái, con phải. Mỗi đường bị đẩy xuống sâu hơn sau mỗi lần chèn, nên tổng công là $O(n \log C)$ lần đẩy cộng $O(n \log C)$ lần gộp.

Xử lý đỉnh theo thứ tự BFS ngược để con xong trước cha, khỏi đệ quy theo cây.

Ví dụNhảy Xuống Lá

Đề. Cây $n \le 10^5$ đỉnh, gốc 1, $|a_i|, |b_i| \le 10^5$. Từ $u$ không phải lá nhảy tới hậu duệ nghiêm ngặt $v$ tốn $a_u b_v$, nhảy tiếp tới khi tới lá. In chi phí nhỏ nhất từ mỗi đỉnh (lá là 0).

Lời giải. $dp_u = \min_v (a_u b_v + dp_v)$ trên mọi hậu duệ nghiêm ngặt $v$, lá có $dp = 0$. Với $u$ cố định, $a_u b_v + dp_v$ là giá trị tại $x = a_u$ của đường $b_v x + dp_v$. Vậy mỗi đỉnh giữ một cây Li Chao chứa đường của mọi đỉnh trong cây con của nó. Cây của $u$ là gộp cây của các con; hỏi tại $a_u$ cho $dp_u$; rồi mới thêm đường của chính $u$, để $u$ không tự nhảy tới chính nó. insert, query là Li Chao động trên $[-10^5, 10^5]$ như ví dụ đầu bài.

Bước 1: gộp hai cây Li Chao. Chèn đường ở gốc y vào cây x, rồi gộp đệ quy hai cặp con. Nút y bị bỏ sau khi đường của nó được chèn vào x; các nút con của y được dùng lại. Mỗi đường chỉ đi xuống sâu hơn sau mỗi lần bị chèn, độ sâu tối đa $O(\log C)$, nên tổng công của mọi lần gộp là $O(n \log C)$.

int merge(int x, int y, ll l, ll r) {
    if (!x || !y) return x | y;
    insert(x, l, r, la[y], lb[y]);
    ll m = (l + r) >> 1;
    lc[x] = merge(lc[x], lc[y], l, m);
    rc[x] = merge(rc[x], rc[y], m + 1, r);
    return x;
}

Bước 2: duyệt từ lá lên. BFS từ gốc lấy par và order; duyệt order từ cuối thì con xong trước cha. Đỉnh không có con là lá, $dp = 0$.

for (int i = n - 1; i >= 0; i--) {
    int u = order[i];
    bool leaf = 1;
    for (int v : adj[u])
        if (v != par[u]) leaf = 0, root[u] = merge(root[u], root[v], L, R);
    dp[u] = leaf ? 0 : query(root[u], a[u]);
    insert(root[u], L, R, b[u], dp[u]);
}

Độ lớn: $|a_u b_v| \le 10^{10}$, đường dài tới $10^5$ bước nên $|dp| \le 10^{15}$, vừa long long. Mỗi lần insert tạo tối đa một nút, nên mảng M = 4e6 nút là dư.

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

const int N = 1e5 + 5, M = 4e6 + 5;
const ll L = -1e5, R = 1e5, INF = LLONG_MAX;
int n, tot, root[N], par[N], lc[M], rc[M];
ll a[N], b[N], dp[N], la[M], lb[M];
vector<int> adj[N];

void insert(int &x, ll l, ll r, ll p, ll q) {
    if (!x) {
        x = ++tot, la[x] = p, lb[x] = q;
        return;
    }
    ll m = (l + r) >> 1;
    bool left = p * l + q < la[x] * l + lb[x], mid = p * m + q < la[x] * m + lb[x];
    if (mid) swap(la[x], p), swap(lb[x], q);
    if (l == r) return;
    if (left != mid) insert(lc[x], l, m, p, q);
    else insert(rc[x], m + 1, r, p, q);
}

int merge(int x, int y, ll l, ll r) {
    if (!x || !y) return x | y;
    insert(x, l, r, la[y], lb[y]);
    ll m = (l + r) >> 1;
    lc[x] = merge(lc[x], lc[y], l, m);
    rc[x] = merge(rc[x], rc[y], m + 1, r);
    return x;
}

ll query(int x, ll p) {
    ll res = INF, l = L, r = R;
    while (x) {
        res = min(res, la[x] * p + lb[x]);
        ll m = (l + r) >> 1;
        if (p <= m) x = lc[x], r = m;
        else x = rc[x], l = m + 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> order = {1};
    for (int i = 0; i < (int)order.size(); i++) {
        int u = order[i];
        for (int v : adj[u])
            if (v != par[u]) par[v] = u, order.push_back(v);
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        bool leaf = 1;
        for (int v : adj[u])
            if (v != par[u]) leaf = 0, root[u] = merge(root[u], root[v], L, R);
        dp[u] = leaf ? 0 : query(root[u], a[u]);
        insert(root[u], L, R, b[u], dp[u]);
    }
    for (int i = 1; i <= n; i++) cout << dp[i] << ' ';
    cout << '\n';
}

ChạyInput6
4 -2 3 5 1 7
2 6 -1 4 3 -5
1 2
1 3
2 4
2 5
3 6

Output-20 -8 -15 0 0 0

$O(n \log C)$ với $C = 2 \cdot 10^5$.