Li Chao Tree (Dynamic Convex Hull Optimization)

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다.

 

실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다.

 

직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다.

#include <bits/stdc++.h> using namespace std; #define MAXN 100005 typedef __int64_t lld; typedef __int128_t lll; int Q; struct LINE{ int a; lld b; lll operator * (const LINE &ot)const{ return (lll)a*ot.b-(lll)ot.a*b; } lld get(int x)const{ return (lld)a*x+b; } lld get(lld x)const{ return a*x+b; } bool operator < (const LINE &ot)const{ return a > ot.a; } }; lll ccw(const LINE &a, const LINE &b, const LINE &c){ return a*b + b*c + c*a; } namespace DS{ set<LINE> st; void add(const LINE &tg){ auto it = st.lower_bound(tg); if (it != st.end() && it->a == tg.a && it->b <= tg.b) return; if (it != st.end() && it->a == tg.a){ auto tmp = it++; st.erase(tmp); } if (it != st.begin() && it != st.end()){ auto l = it; l--; auto r = it; if (ccw(*l, tg, *r) >= 0) return; } for (;;){ if (it == st.begin()) break; auto l2 = it; l2--; if (l2 == st.begin()) break; auto l1 = l2; l1--; if (ccw(*l1, *l2, tg) >= 0) st.erase(l2); else break; } for (;;){ auto r1 = it; if (r1 == st.end()) break; auto r2 = it; r2++; if (r2 == st.end()) break; if (ccw(tg, *r1, *r2) >= 0) st.erase(r1); else break; it = r2; } st.insert(tg); } lld get(lld x){ // 최소값을 구함 LINE t = *st.rbegin(); int s = t.a+1, e = st.begin()->a; while (s <= e){ int m = s+e>>1; auto it = st.lower_bound({m, 0}); auto it2 = it; it2++; if (it2 != st.end() && it->get(x) >= it2->get(x)) e = m-1; else s = m+1, t = *it; } return t.get(x); } }; int main() { for (scanf("%d", &Q);Q--;){ int t; scanf("%d", &t); if (t == 1){ int a; lld b; scanf("%d%lld", &a, &b); // 자료구조가 최소값을 구하도록 되어있어, // 최대값을 구하기 위해 함수를 negation 해서 넣는다. DS::add({-(int)a, -b}); }else{ lld x; scanf("%lld", &x); // 결과값도 negation 해서 출력한다. printf("%lld\n", -DS::get(x)); } } }

 

Segment tree를 이용하여, 직선들을 관리해주어 128비트 정수형과 실수형 변수 없이 효과적으로 이 문제를 해결할 수 있는 Li Chao tree에 대해 알아보자.

 

Li Chao tree는 Segment tree에서 정점을 동적으로 만들어가며, 각 구간마다 제일 의미 있는 직선에 대한 정보를 가지고 있는 Segment tree의 응용이라고 볼 수 있다. 질의로 들어올 수 있는 x 좌표의 범위가 [S, E]라고 할 때, Li Chao tree의 루트 정점은 구간 [S, E]를 관리한다.

 

Li Chao tree의 구간 [s, e]를 대표하는 어떤 정점에 직선 $y = ax + b$를 갱신하는 상황을 보자. $x = s$일 때 직선의 y 좌표의 값이 낮은 직선을 low, 큰 직선을 high라고 보면 다음과 같이 3가지 상황이 있을 수 있다.

 

상황 1. 구간 [s, e]에서 high가 모두 큰 경우

이때, 정점의 직선을 high로 바꿔주고, 더 이상의 추가 작업은 없다.

 

상황 2. low와 high의 교점이 왼쪽에 있는 경우

이 경우 low 직선이 [s, e] 구간의 대부분에서 큰 값을 가지므로 정점의 직선을 low로 바꿔주고, 왼쪽 구간의 정점에 high를 갱신해주는 작업을 재귀적으로 이어나간다.

 

상황 3. low와 high의 교점이 오른쪽에 있는 경우

마찬가지로, 이 경우 high 직선이 [s, e] 구간의 대부분에서 큰 값을 가지므로 정점의 직선을 high로 바꿔주고, 오른쪽 구간의 점점에 low를 갱신해주는 작업을 재귀적으로 이어나간다.

 

직선이 추가되는 경우 위와 같이 Segment tree에 갱신 작업을 이어나가는 경우, 전체 구간 [S, E]의 크기를 $X$라 할 때, 시간복잡도는 최대 $O(\lg X)$가 된다.

 

어떤 x 좌표 $x$에 대해 가장 큰 $y$ 값을 구하고 싶다면, top-down 방식으로 정점의 직선 $y = ax + b$에 $x$ 값을 넣어 $y$ 값을 구하고, 방문하는 정점 중 가장 큰 $y$ 값을 구하면 된다. 이때 시간복잡도 또한 $O(\lg X)$가 된다.

 

구현은 다음과 같이 할 수 있다.

#include <bits/stdc++.h> using namespace std; typedef long long lld; struct LiChaoTree{ static const lld inf = 1e18; struct Line{ int a; lld b; lld get(lld x)const{ return a*x+b; } }; struct Node{ int l, r; Line line; }; const lld S, E; vector<Node> tree; LiChaoTree(lld S, lld E): S(S), E(E) { tree.push_back({-1, -1, {0, -inf}}); } void update(int now, lld s, lld e, const Line &t){ Line low = t, high = tree[now].line; if (low.get(s) > high.get(s)) swap(low, high); if (low.get(e) <= high.get(e)){ tree[now].line = high; return; } lld m = s+e >> 1; if (low.get(m) <= high.get(m)){ tree[now].line = high; if (tree[now].r < 0){ tree[now].r = tree.size(); tree.push_back({-1, -1, {0, -inf}}); } update(tree[now].r, m+1, e, low); }else{ tree[now].line = low; if (tree[now].l < 0){ tree[now].l = tree.size(); tree.push_back({-1, -1, {0, -inf}}); } update(tree[now].l, s, m, high); } } void add(const Line &t){ update(0, S, E, t); } lld get(int now, lld s, lld e, lld x)const{ if (now == -1) return -1e18; lld m = s+e >> 1; if (x <= m) return max(tree[now].line.get(x), get(tree[now].l, s, m, x)); else return max(tree[now].line.get(x), get(tree[now].r, m+1, e, x)); } lld get(lld x)const{ return get(0, S, E, x); } }; int Q; int main() { const lld MAX = 1e12; LiChaoTree ds(-MAX, MAX); for (scanf("%d", &Q);Q--;){ int t; scanf("%d", &t); if (t == 1){ int a; lld b; scanf("%d%lld", &a, &b); ds.add({a, b}); }else{ lld x; scanf("%lld", &x); printf("%lld\n", ds.get(x)); } } }

 

예시 문제의 경우 질의로 주어지는 $x$ 좌표가 정수이므로, 정수에 맞춰 구현을 했다. 만약, 질의로 실수가 들어오는 경우는 Segment tree 구현을 다르게 해야 한다. 만약, 최댓값을 구하는 게 아니라, 최솟값을 구하고 싶은 경우, 이와 비슷한 방식으로 새로 구현하거나, 위 코드에서 넣는 직선의 기울기와 y절편 값을 negation 하는 것으로 간단하게 구할 수 있다.

 

* 응용 방법

기존에는 stack이나 set을 이용했지만, Li Chao 트리에서는 Segment tree를 이용하므로, Persistent Segment tree와 같은 응용 버전을 생각해볼 수 있다. 이런 문제를 아직까지 실제로 본 적은 없다.