리 차오 트리

직선 집합 위의 최솟값 질의

여러 직선 \(f_k(x)=a_k\ x + b_k\) 가 있을 때 임의의 \(x\) 에서 \(\min_k f_k(x)\) (또는 \(\max\))를 구하는 문제는 DP 최적화의 단골이다. 예를 들어

$$ dp[i] = \min_j\big(dp[j] + a_j\cdot x_i + b_j\big) $$

처럼 전이가 "직선의 점 평가"로 쓰이는 경우다. 기울기와 질의가 모두 단조라면 단순 Convex Hull Trick(스택)으로 \(O(1)\) 균등 처리가 가능하지만, 임의 순서로 직선이 추가되고 임의의 \(x\) 가 질의 되면 정렬 가정이 깨진다. Li Chao 트리가 이 동적 상황을 처리한다.

핵심 아이디어

\(x\) 의 정의역 \([L,R]\) 위에 세그먼트 트리를 세운다. 각 노드는 "그 구간에서 가장 자주 최소가 되는 직선" 하나를 들고 있다. 새 직선 \(g\) 를 노드 구간 \([l,r]\) 에 삽입할 때:

1. 중점 \(m=(l+r)/2\) 에서 기존 직선 \(f\) 와 \(g\) 를 비교, 중점에서 더 낮은 쪽을 노드에 남긴다.
2. 끝점 \(l\) 에서의 우열을 보고, 노드에 진 쪽을 한쪽 자식으로 내려보낸다. 두 직선은 한 번만 교차하므로(선형) 한쪽 절반에서만 역전될 수 있다.

이렇게 하면 각 노드에는 항상 그 구간 중점에서 우세한 직선이 남고, 패배한 직선은 자신이 우세할 수 있는 절반으로만 내려간다.

정확성 스케치

두 직선은 많아야 한 점에서 교차한다. 노드 구간을 중점 기준 두 절반으로 나누면, 진 직선이 다시 우세해질 수 있는 곳은 둘 중 한 절반에 통째로 들어간다. 따라서 진 직선을 그 절반의 자식으로 내려보내면 손실이 없다. 깊이 \(O(\log V)\) (\(V\) = 좌표 범위)마다 \(O(1)\) 비교이므로 삽입/질의 모두 \(O(\log V)\).

질의

점 \(x\) 질의는 루트→리프 경로의 모든 노드 직선을 평가해 최솟값을 취한다. 경로 길이가 \(O(\log V)\).

CHT 비교표

좌표가 실수이거나 매우 크면 좌표 압축 또는 동적(포인터) 노드 할당으로 정의역을 다룬다.

배열 기반 구현 (최솟값)

좌표 정의역 \([L,R]\) 위에서 직선 추가/점 질의를 지원한다. 최댓값이 필요하면 직선의 부호를 뒤집거나 비교를 반대로 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;

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

struct LiChao {
    struct Node { Line line; int l = -1, r = -1; };
    vector<Node> t;
    ll L, R;
    LiChao(ll L, ll R) : L(L), R(R) { t.push_back({{0, INF}}); } // 항등(무한대) 직선

    void insert(int node, ll l, ll r, Line nw) {
        ll m = l + (r - l) / 2;
        bool left = nw.eval(l) < t[node].line.eval(l);   // 왼끝 우열
        bool mid  = nw.eval(m) < t[node].line.eval(m);   // 중점 우열
        if (mid) swap(t[node].line, nw);                 // 중점 승자를 남긴다
        if (l == r) return;
        if (left != mid) {                               // 패자는 왼쪽 절반으로
            if (t[node].l == -1) { t[node].l = t.size(); t.push_back({{0, INF}}); }
            insert(t[node].l, l, m, nw);
        } else {                                         // 또는 오른쪽 절반으로
            if (t[node].r == -1) { t[node].r = t.size(); t.push_back({{0, INF}}); }
            insert(t[node].r, m + 1, r, nw);
        }
    }
    void add(Line nw) { insert(0, L, R, nw); }

    ll query(int node, ll l, ll r, ll x) {
        if (node == -1) return INF;
        ll res = t[node].line.eval(x);
        if (l == r) return res;
        ll m = l + (r - l) / 2;
        if (x <= m) return min(res, query(t[node].l, l, m, x));
        else        return min(res, query(t[node].r, m + 1, r, x));
    }
    ll query(ll x) { return query(0, L, R, x); }
};

자주 하는 실수

• 정수 오버플로. \(a\cdot x\) 가 64비트를 넘으면 __int128 비교가 필요하다. 초기 직선 \(b=INF\) 가 \(eval\) 에서 넘치지 않게 \(INF\)를 보수적으로 잡는다.
• 최댓값 혼동. 최댓값 CHT는 비교를 > 로 바꾸고 항등 직선을 \(-INF\) 로 둔다. 부등호와 항등값을 한 세트로 바꾸지 않으면 미묘한 버그가 난다.
• 정의역 누락. 질의 \(x\) 가 \([L,R]\) 밖이면 결과가 틀린다. 압축 좌표를 쓸 때 범위를 충분히 넓게.
• left/mid 분기. left != mid 일 때만 왼쪽으로 내려간다는 규칙을 정확히 지켜야 한다.

응용

확장: 구간 삽입 Li Chao

세그먼트 트리처럼 \([lo,hi]\) 구간에만 직선을 추가하려면, 표준 세그 분해로 \(O(\log V)\) 개 노드 각각에 직선을 삽입하면 된다(노드당 \(O(\log V)\), 총 \(O(\log^2 V)\)). 시간축에 직선이 생겼다 사라지는 오프라인 문제에 유용하다.