Li Chao Tree 공부

어떤 기술 X의 사용 범위를 R(X)라 나타내자.

R(Convex Hull Tree ) < R( Monotone Queue Optimization ) < R( Li Chao Tree )

 

Li Chao Tree의 구현이 가장 간단하다

위 2개의 말을 PS 장인 친구 ^[각주:1]로부터 들었다.

 

따라서 Li Chao Tree를 공부한다.

(숨겨진 전제 : 1. PS장인이 해준 말은 믿을만 하다. 2. 가장 범용성 있고 구현이 간단한 자료구조 공부는 필수다.)

 

 

설명

구현

 

리차오 트리는 Li Chao Segment Tree라고도 불린다.

CHT는 각 직선들의 기울기가 증가하는 순서대로 주어질 때만 관리가 가능하지만

리차오 트리는 기울기 값이 정렬되어 있지 않을 때도 관리가 가능하다. 즉, 온라인 쿼리 처리 기법이다.

 

리차오 트리에서 가능한 연산은 두 가지다.

 

1. 함수 삽입

2. 주어진 $x$좌표에서 함숫값의 최댓값

 

1번에서 삽입하는 함수는 서로 다른 함수 간 교점이 최대 1개여야 하며,

일반적으로 $y = ax + b$꼴 일차함수를 의미한다.

 

여기서 일차함수를 다룬다. 

설명은 다른 블로그에 자세히 되어 있으니 생략한다.

내가 공부했으니 된 것. ㅎㅎ

 

다음은 반평면 땅따먹기 코드다

 

/*
solution here
 
*/
 
#include<bits/stdc++.h>
using namespace std;
 
#define nl '\n'
#define sp ' '
using ll = long long;
ll inf = 2e18;
 
struct Line
{
    ll a,b;
    ll get(ll x)
    {return a*x+b;}
};
 
Line base = {0,-inf};
 
struct Node
{
    int l,r;
    ll s,e;
    Line v;
};
 
struct Lichao
{
    vector<Node> tree;
 
    Lichao(ll s=-2e12,ll e=2e12)
    {
        push(s,e);
    }
 
    inline void push(ll s,ll e)
    {
        tree.push_back({-1,-1,s,e,base});
    }
 
    bool cmp(Line a,Line b,ll x)
    {
        return a.get(x)>b.get(x);
    }
 
    void update(int nd,Line v)
    {
        Node t = tree[nd];
        ll s = t.s, e = t.e;
        Line low = t.v, high = v;
 
        if(cmp(low,high,s))
            swap(low,high);
 
        if(!cmp(low,high,e))
        {
            tree[nd].v = high;
            return;
        }
        ll m = s+e >> 1;
 
        /*
            m에서 high가 더 크면 왼쪽에 high 넘기고 오른쪽 업데이트
        */
        if(cmp(high,low,m))
        {
            tree[nd].v=high;
            if(tree[nd].r==-1)
            {
                tree[nd].r=tree.size();
                push(m+1,e);
            }
            update(tree[nd].r,low);
        }
        else
        {
            tree[nd].v=low;
            if(tree[nd].l==-1)
            {
                tree[nd].l=tree.size();
                push(s,m);
            }
            update(tree[nd].l,high);
        }
    }
    ll query(int nd,ll x)
    {
        if(nd==-1) return -inf;
        Node t = tree[nd];
        ll m = t.s + t.e >> 1;
        int nxt = x<=m ? t.l : t.r;
        return max(t.v.get(x),query(nxt,x));
    }
};
 
void solve()
{
    int q; cin>>q;
    Lichao f;
    while(q--)
    {
        ll op,a,b;
        cin>>op;
        if(op==1)
        {
            cin>>a>>b;
            f.update(0,{a,b});
       }
        else
        {
            cin>>a;
            cout<<f.query(0,a)<<nl;
        }
    }
}
int main()
{
    ios::sync_with_stdio(!cin.tie(0));
    solve();
}
 

1. cgiosy  [본문으로]