Li Chao Tree (Dynamic Convex Hull Optimization)

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

 

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

 

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#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)$가 된다.

 

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

#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와 같은 응용 버전을 생각해볼 수 있다. 이런 문제를 아직까지 실제로 본 적은 없다.