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

실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(<a href="https://www.acmicpc.net/problem/12795">반평면 땅따먹기</a>)로 설명을 이어가겠다.

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


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가 모두 큰 경우
<figure data-filename="경우1.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/de5Mal/btqZpfk1Qaj/GAPSkWFzlqbJaA3K9SHJP0/img.png" data-filename="경우1.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"></figure>
이때, 정점의 직선을 high로 바꿔주고, 더 이상의 추가 작업은 없다.

상황 2. low와 high의 교점이 왼쪽에 있는 경우
<figure data-filename="경우2.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/OOwpf/btqZpT3aH0t/BfU1AKIvlDU966OsbrdsBk/img.png" data-filename="경우2.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"></figure>
이 경우 low 직선이 [s, e] 구간의 대부분에서 큰 값을 가지므로 정점의 직선을 low로 바꿔주고, 왼쪽 구간의 정점에 high를 갱신해주는 작업을 재귀적으로 이어나간다.

상황 3. low와 high의 교점이 오른쪽에 있는 경우
<figure data-filename="경우3.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"><img src="https://blog.kakaocdn.net/dn/byzT7u/btqZoyLYhoA/OQk1N4Avgjto62wiz5oMGk/img.png" data-filename="경우3.png" data-origin-width="664" data-origin-height="590" width="524" height="NaN" data-ke-mobilestyle="widthContent"></figure>
마찬가지로, 이 경우 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)$가 된다.

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


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

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

PS 이야기

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

Li Chao Tree (Dynamic Convex Hull Optimization)

댓글