리차오 트리의 정상화

1. 리차오 트리

리차오 트리는 주로 CHT(Convex Hull Trick)이라 불리는 다음과 같은 문제에 사용된다.

• 직선 $ax + b$ 추가
• $x$가 주어질 때 직선들 중 $ax + b$의 최댓값 쿼리

물론 최솟값 쿼리 또한 해결 가능하다.

이때 직선의 기울기 $a$가 단조증가/단조감소하고, 쿼리로 주어지는 $x$가 단조증가/단조감소 하는 경우 스택을 이용한 업데이트, 쿼리 amortized $O(1)$ 해법이 존재한다(https://justicehui.github.io/hard-algorithm/2019/01/25/CHT/). 

 

리차오 트리는 단조 조건이 없는 경우에도 사용할 수 있지만, 업데이트와 쿼리가 $O(\log X)$ ($X$는 쿼리로 주어지는 수의 범위)가 걸린다는 단점이 있다. 단조 조건이 있는 경우 스택 CHT를 사용하도록 하자.

 

편의상 최대화 문제에 대해 생각하자.

 

리차오 트리는 세그먼트 트리의 구조를 사용한다. 트리의 노드 $v$는 어떤 구간 $[L_v, R_v]$을 관리하고, 어떤 직선 $a_v x + b_v$을 저장하고 있다. 이 직선은 노드가 관리하는 구간 중 $M_v = \lfloor \frac{L + R}{2} \rfloor$, $[L_v, M_v]$또는 $[M_v, R_v]$에서 다른 모든 직선과 비교했을 때 최댓값을 가진다 (즉 직선이 최댓값을 가지는 구간은 연속적이며 한쪽 끝을 포함한다).

made with chatGPT

쿼리를 어떻게 처리할지부터 생각해보자.

결론적으로 말하자면 $x$가 주어지면 루트 노드에서부터 시작하여 $x$가 포함되는 구간을 관리하는 모든 노드 $v$에 대하여 $a_v x + b_v$를 계산하면 그 중 최댓값이 우리가 원하는 값이 된다. 이는 그러한 직선들 중 $x$에서 최댓값을 가지는 직선이 적어도 하나 존재할 것이기 때문이다. 이는 위에서 설명한 리차오 트리의 구조에 의해 참이다.

 

모든 노드의 직선을 $0 \cdot x -\infty$으로 초기화하고 직선 $a_i x + b_i$에 대한 업데이트를 처리해보자.

루트에서부터 재귀적으로 처리한다. 현재 보고 있는 노드를 $v$라 하자. 우선 이 직선이 $v$에 저장된 직선 $a_v x + b_v$보다 큰 구간이 $[L_v, R_v]$에 존재하는지 확인해야한다. 

가령 이런 경우에서는 직선 $i$가 의미 없는 직선일 것이다. $v$와 $i$가 바뀌었다면 $v$가 의미 없는 직선일 것이다. 이러한 경우를 예외처리 해주며 그 직선을 버려주고 재귀를 종료해주자.

 

일반성을 잃지 않고 $M_v = \lfloor \frac{L + R}{2} \rfloor$, $a_v M_v + b_v \geq a_i M_v + b_i$라 해주자. 만약 직선 $i$가 $L_v$에서 더 크다면 왼쪽 노드로, $R_v$에서 더 크다면 오른쪽 노드로 직선을 옮겨주는 재귀 호출을 해주면 된다. 이는 두 직선의 교점은 하나이고 그러한 경우에서 $v$에 저장된 직선이 리차오 트리의 조건인 절반 이상에서 최댓값을 가짐을 만족하기 때문이다. 

 

쿼리로 주어지는 $x$의 범위가 너무 크면 어떻게 해야할까? 그냥 동적 세그먼트 트리를 짜거나 오프라인 쿼리가 허용될 경우 좌표압축을 사용하면 된다. 

 

동적 리차오 트리의 경우 직선을 리프까지 밀어주지 않아도 된다는 장점이 있다. 즉 $O(Q)$의 메모리만을 요구한다($Q$는 업데이트 횟수).

 

다음은 https://www.acmicpc.net/problem/12795 을 동적 리차오 트리로 해결하는 cpp 코드이다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll INF = 2e18;

struct Line{
    ll a = 0, b = -INF;
    ll f(ll x){
        return a * x + b;
    }
};

class LCT{
    private:
    vector<int> l, r;
    vector<Line> node;

    public:
    LCT(){ l.resize(2), r.resize(2), node.resize(2); }

    void update(Line li, int i=1, ll s=-1e12, ll e=1e12){
        if(li.f(s) > node[i].f(s)) swap(li, node[i]);
        if(li.f(e) <= node[i].f(e)) return;

        ll m = (s + e) >> 1;
        if(li.f(m) > node[i].f(m)) swap(li, node[i]);
        
        if(li.f(s) > node[i].f(s)){
            if(!l[i]){
                node.push_back(li);
                l[i] = node.size() - 1;
                l.push_back(0), r.push_back(0);
            }
            else{
                update(li, l[i], s, m);
            }
        }
        else{
            if(!r[i]){
                node.push_back(li);
                r[i] = node.size() - 1;
                l.push_back(0), r.push_back(0);
            }
            else{
                update(li, r[i], m + 1, e);
            }
        }
    }

    ll query(ll x, int i=1, ll s=-1e12, ll e=1e12){
        if(x < s || x > e || !i) return -INF;
        ll ret = node[i].f(x);
        ll m = (s + e) >> 1;
        if(x <= m) return max(ret, query(x, l[i], s, m));
        else return max(ret, query(x, r[i], m + 1, e));
    }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(nullptr);
    int q;
    cin >> q;
    LCT lct;
    while(q--){
        int asd;
        cin >> asd;
        if(asd == 1){
            ll a, b;
            cin >> a >> b;
            lct.update({a, b});
        }
        else{
            ll x;
            cin >> x;
            cout << lct.query(x) << '\n';
        }
    }
}

 

리차오 트리는 스택 CHT보다 코드는 길지만 보다 단순하고 세그에 익숙하면 뇌를 빼고 짤 수 있다는 점이 장점이다.

 

2. 직선 삭제가 가능한 리차오 트리

이는 크게 2가지 방법이 있다. 

오프라인 쿼리가 가능할 경우 직선이 살아있는 구간을 구해주고 오프라인 동적 연결성의 아이디어를 가져와 사용하면 된다.

온라인 쿼리일 경우 바로 전에 삽입된 직선만 제거해줄 수 있는데, 이는 그냥 PST로 짜면 된다.

 

3. 리차오 트리의 일반화

리차오 트리는 DNC 최적화나 monotone queue 최적화에 사용할 수 있다. 이는 위에서 설명한 리차오 트리의 업데이트에서 직선에 대해 우리가 사용한 조건이 교점이 하나인 것 밖에 없기 때문이다. monge 행렬 $C[i][j]$에 대해 $f_i(j) = C[i][j]$라 하면 이러한 함수들은 교점이 하나임이 알려져 있다 (https://koosaga.com/242 3. Monotone Queue Optimization 참고) 정확히는 교점이 하나의 구간을 이룬다(값이 같을 수 있기에). 

 

https://www.acmicpc.net/problem/30476

이 문제는 유명한 dnc opt문제 중 하나인 money for nothing(https://www.acmicpc.net/problem/14636)의 온라인 쿼리 버전이다. 제곱근 분할을 하면 해결할 수 있다고 하는데(나는 이 풀이를 잘 모른다) 그냥 리차오 트리를 짜도 된다. 다만 함수가 살아있는 구간에 신경을 써주며 업데이트를 해야 하는데 이게 조금 까다로울 수는 있다.