Convex hull trick과 Li-Chao tree

Convex hull trick은 여러 개의 일차함수들이 있을 때, 어떤 $x$좌표에서의 최댓값 혹은 최솟값을 빠르게 구하기 위해 사용할 수 있는 방법이다. CHT라고 부르기도 한다.

일차함수는 다양한 특징을 가져서 비교적 쉽게 관리할 수 있고, 그래서 문제에도 많이 나온다. 일차함수의 최댓값 문제에서 중요하게 사용되는 성질들은 다음과 같다.

1. 여러 일차함수들이 있을 때, 이들의 최댓값을 $m(x)$라고 하면, 각 일차함수 $f(x)$에 대해 $m(x)=f(x)$인 $x$값은 닫힌 구간($\pm\infty$을 포함)으로 표현된다.

증명 생략.

2. 일차함수는 볼록하다.

$\frac{f(x)+f(y)}{2}=f(\frac{x+y}{2})$이므로 볼록하면서 오목하다.

3. 일차함수들의 최댓값은 볼록하다. 일반적으로 볼록함수들의 최댓값은 볼록하다.

$\frac{f(x)+f(y)}{2}\geq f(\frac{x+y}{2})$, $\frac{g(x)+g(y)}{2}\geq g(\frac{x+y}{2})$를 만족하는 두 볼록함수가 있다고 하자.

$\frac{max(f(x), g(x))+max(f(y), g(y))}{2}\geq \frac{f(x)+f(y)}{2}\geq f(\frac{x+y}{2})$

$\frac{max(f(x), g(x))+max(f(y), g(y))}{2}\geq \frac{g(x)+g(y)}{2}\geq g(\frac{x+y}{2})$

위의 두 식에 의해 

$\frac{max(f(x), g(x))+max(f(y), g(y))}{2}\geq max(f(\frac{x+y}{2}), g(\frac{x+y}{2}))$이므로 볼록하다.

 볼록하다는 말은 엄밀하지 않게는 기울기가 증가한다고 말할 수도 있다. 최댓값에 관여되는 일차함수들을 기울기 순서대로 늘어놓으면 각 일차함수들이 관여하는 구간들이 증가하게 되고, 일차함수들을 기울기 순서대로 일렬로 늘어놓고 관리하면 이분탐색을 통해 특정 $x$값에서의 최댓값을 찾을 수 있다.

 이 성질들을 이용하여 다음과 같은 Convex hull trick을 생각할 수 있다. 뒤에서 나오는 $N$은 삽입 연산의 횟수, $Q$는 최댓값 쿼리의 개수이다.

A. Incremental convex hull trick

 일차함수의 삽입 연산과 $x$에서의 최댓값 쿼리가 있다고 하자.

 일차함수들을 기울기 순서대로 배열에 넣어서 관리한다고 생각하자. 단, $m(x)=f(x)$인 $x$가 없는 $f(x)$는 무효하기 때문에 없는 것 취급한다.

 새로운 일차함수를 삽입한다면, 삽입되는 일차함수의 기울기를 기준으로 삽입될 위치를 결정할 수 있다. 삽입 후의 일차함수 배열을 $l_i$라고 하자. 다음과 같은 경우가 생길 수 있다.

1. $l_i$가 무효하다.

 $l_i$가 $max(l_{i-1}, l_{i+1})$보다 작다면 $l_i$는 무효하다. 이 때는 삽입을 하지 않아야 한다.

2. $l_{i-1}$이나 $l_{i+1}$이 무효하다.

 $l_i$의 삽입으로 인해 바로 옆의 일차함수가 무효하게 된 경우이다. 이 경우에는 그 일차함수를 지운 후 $l_i$를 다시 삽입한다. 이 경우에 무조건 일차함수가 1개씩 사라지므로 amortized $O(N)$번의 연산만이 사용된다.

3. $l_{i-1}$, $l_i$, $l_{i+1}$이 모두 무효하지 않다.

 세 일차함수가 모두 유효하다면, $l_i$가 다른 일차함수들에는 영향을 미치지 않는다. 따라서 그 자리에 그대로 삽입할 수 있다.

 이 배열을 BBST로 관리한다면 2번 연산을 amortized $O(NlogN)$, 나머지 연산을 $O(logN)$에 처리할 수 있다. $x$에서의 최댓값 쿼리도 $O(logN)$에 처리할 수 있다.

 이 방법은 어떤 일차함수가 들어오던 온라인으로 삽입하고 쿼리하는 것이 가능하다. 그러나 BBST의 특성상 $O(logN)$이지만 느리고 복잡하다. 또 제거가 불가능하다는 문제점이 있다. 구현을 단순하게 하기 위해서 삽입되는 일차함수나 쿼리로 들어오는 $x$좌표에 제한 조건을 둘 수 있다.

B. Incremental convex hull trick (increasing query)

 쿼리로 들어오는 $x$좌표가 단조 증가 또는 감소한다면, 쿼리를 좀 더 간단하게 구현할 수 있다. $x$좌표가 증가한다는 의미는 $x$보다 작은 쿼리는 더 이상 들어오지 않는다는 것을 의미한다. 가장 왼쪽의 두 일차함수 $l_1$, $l_2$를 보자. $l_1$이 관리하는 구간은 $(-\infty, X_1]$, $l_2$가 관리하는 구간은 $[X_1, X_2]$일 것이다. 만약 $x\leq X_1$이라면 $l_1$의 값이 최댓값이 된다. $x>X_1$이라면 앞으로의 모든 쿼리에서 $x>X_1$이 되고, $l_1$은 더 이상 사용되지 않게 된다. 따라서 $l_1$을 지워버리고 위의 과정을 반복할 수 있다.

 이 때의 쿼리당 시간복잡도는 $x\leq X_1$일 때 $O(logN)$이고, $x>X_1$일 때 일차함수가 무조건 하나 사라지므로 amortized $O(NlogN)$이다. 총 시간복잡도 $O(NlogN+Q)$로 처리할 수 있다.

C. Incremental convex hull tick (increasing slope)

 삽입되는 일차함수의 기울기가 단조 증가 또는 감소한다면, BBST 없이도 구현이 가능하다. $f(x)$의 삽입 연산이 들어왔다면, 이미 삽입된 일차함수들의 기울기는 $f(x)$의 기울기 이하일 것이다. 가장 기울기가 큰 일차함수가 관리하는 구간은 $[X, \infty)$가 될 것이고, 따라서 새로 추가된 일차함수에 의해 제거되는 일차함수들은 오른쪽의 몇 개일 것이다. 가장 오른쪽에 있는 일차함수 두 개와 새로 삽입될 일차함수를 비교하여 가장 오른쪽에 있는 일차함수가 무효하다면 그 일차함수를 제거하고 반복하면 되고, 무효하지 않다면 가장 오른쪽에 일차함수를 삽입하면 된다. 이것은 스택을 이용하여 관리할 수 있고, 일차함수 삽입의 시간복잡도는 amortized $O(1)$이 되고, 쿼리의 시간복잡도는 $O(logN)$이 된다.

 이분탐색을 통해 오른쪽에서 제거될 일차함수의 개수를 $O(logN)$에 찾아서 한 번에 제거할 수도 있다. 이것을 배열을 이용하여 구현하면 amortized가 붙지 않는 대신 일차함수 삽입의 시간복잡도가 $O(logN)$이 된다.

D. Persistent incremental convex hull trick

 A, B, C의 BBST나 스택을 persistent하게 구현하여 사용할 경우, CHT를 persistent하게 사용할 수 있다.

E. Offline dynamic convex hull trick

 일차함수의 제거를 처리하기 위해서 오프라인으로 segment tree를 이용할 수 있다.

 segment tree를 시간 기준으로 만들면 각 노드들은 $[s_i, e_i]$를 관리하는 노드가 될 것이다. 각각의 노드들을 A, B, C와 같은 자료구조로 만들어 각각이 CHT를 처리할 수 있도록 만든다.

 오프라인 알고리즘이기 때문에 각각의 일차함수들이 관여하는 시간을 구간 $[u_i, v_i]$로 표현할 수 있다. $[u_i, v_i]$에 포함되는 가장 높은 $O(logN)$개의 노드에 해당 일차함수를 삽입하면 각 노드의 시간복잡도$\times O(logN)$에 삽입을 처리할 수 있다.

 쿼리 또한 쿼리가 들어온 시간 $t$를 포함하는 $O(logN)$개의 노드들에 쿼리를 해서 모두 합쳐주면 각 노드의 시간복잡도$\times O(logN)$에 쿼리를 처리할 수 있다.

 segment tree를 시간 기준으로 만드는 대신 $x$좌표 기준으로 만들 경우 일차함수(직선)이 아닌 선분의 삽입을 처리하는 것도 가능한 등, segment tree를 통해 다양한 문제를 해결할 수 있다.

F. Li-Chao tree

 Convex hull trick 글에 썼지만 Convex랑 관련이 없다...

 Li-Chao segment tree라고도 부르는 것 같다. 이름에서 볼 수 있듯 segment tree의 일종인데, 각 노드들은 $x$좌표 $[s_i, e_i]$를 관리하며, 하나의 일차함수를 가지고 있다.

 Li-Chao tree가 사용될 수 있는 상황은 쿼리로 들어오는 $x$좌표가 유한한 경우로, 보통 쿼리들을 모두 알고 있거나, 쿼리가 범위가 정해진 정수일 때 사용할 수 있다.

 최댓값을 구하고자 할 때, Li-Chao tree의 초기 상태는 모든 노드가 $z(x)=0x-\infty$를 가지고 있는 상태이다. 이 트리에서 쿼리 $x$에서의 최댓값을 구하기 위해서는 $x$를 포함하는 $O(logX)$ 모든 노드에서의 $f(x)$ 값의 최댓값을 가져오면 된다.

 이제 Li-Chao tree가 위의 성질을 유지하도록 새로운 일차함수를 삽입하자.

 $[x_s, x_e]$를 관리하는 노드에 $f(x)$가 삽입된다고 가정하자. 일차함수가 관리하는 $x$가 구간으로 나타나기 때문에 노드에 있던 일차함수와 새로운 일차함수 중에서 단 하나의 일차함수가 관리하는 구간만이 $x_m (m=\frac{s+e}{2})$을 포함한다.

 $x_m$가 관리하는 구간에 포함된다는 뜻은, 나머지 하나의 일차함수는 $x_m$의 왼쪽이나 오른쪽 중 하나만을 관리한다는 의미가 된다. 따라서 나머지 하나의 일차함수가 관리하는 구간은 $L=[x_s, x_m)$ 또는 $R=(x_m, x_e]$에 포함된다. $L$에 포함될 경우에는 왼쪽 자식 노드, $R$에 포함될 경우에는 오른쪽 자식 노드에 재귀적으로 삽입해줄 수 있다.

 계속해서 재귀적으로 삽입하면 쿼리로 가능한 $x$좌표의 유한성으로 인해 $x_s=x_e$인 노드가 나타나고, 원래 있던 일차함수와 새로 삽입된 일차함수 중 하나가 무효해지는 순간이 발생하게 된다. 이 때 재귀를 중지할 수 있다.

 $x$좌표로 가능한 경우의 수를 $X$라고 할 때, Li-Chao tree의 시간복잡도는 삽입, 쿼리가 각각 $O(logX)$가 된다. Li-Chao tree도 E의 segment tree를 이용한 것과 똑같이 선분을 삽입하는 것이 가능한데, 이 때 시간복잡도는 $O(log^2X)$가 된다.

  $f(x)=ax+b$일 때 A부터 E까지의 방법은 두 일차함수의 교점을 비교하는 과정이 필요하다. 교점을 정확히 비교하기 위해 정수 자료형을 사용할 경우 자료형의 범위가 $a\times b$를 포함해야 하는데, 많은 DP 문제에서 $a, x\leq 10^9$, $b>10^{10}$의 범위가 나와서 어쩔수 없이 실수 자료형을 사용하게 된다. 그러나 Li-Chao tree는 함수의 함수값만을 비교하기 때문에 실수 자료형을 사용하게 되는 경우가 잘 발생하지 않는다.

 Li-Chao tree도 segment tree의 일종이기 때문에 동적으로 구성할 수 있다. Li-Chao tree의 특이한 점은 동적으로 트리 압축 없이 구성해도 공간복잡도가 $O(Q)$라는 것이다.