Li Chao Tree

Li Chao Tree는 일차함수들의 볼록 껍질을 관리하는 자료 구조로, 기울기가 단조성을 보이지 않는 경우의 CHT 문제들을 해결하기 위하여 사용된다.

 

https://cp-algorithms.com/geometry/convex_hull_trick.html

 

기본적인 꼴은 segment tree와 동일하다.

각 노드에는 그 노드의 구간을 담당하는 직선이 하나씩 있는데, 이때 주의할 점이 이 구간에서 이 직선이 항상 최대라는 것이 아니라 최댓값 후보 직선들 중 하나라는 것이다. 

 

업데이트는 그 구간에 이미 들어 있던 직선과 지금 직선의 양 끝 부분의 함숫값을 비교한다. 만약 함숫값이 어느 하나가 양쪽 모두 크다면, 전체 구간에서 다 큰 것이기 때문에, 유지하던가, 갱신한다. 하지만 그것이 아니라면 원래 있던 직선은 놔두고 지금 추가할 직선을 양쪽 자식으로 뿌려 준다. 이때 중요한 것은 두 직선은 어디선가 교차할 것인데, 교차점을 포함하지 않는 반쪽 구간은 두 직선 간의 최댓값이 정해지므로 각 단계에서 전체 길이의 1/2 씩 제거해 나갈 수 있다는 것이다. 이를 이용하면 $O(logM)$ 만에 업데이트 할 수 있다. 

 

쿼리는 단순히 해당 점에 해당하는 모든 노드들을 다 방문하며 그 중 최댓값을 반환하면 된다.

 

이와 같이 구현은 좌표의 범위가 클 수도 있으므로 dynamic segment tree를 구현하면 되고, 전체 시간 복잡도는 좌표 크기에 비례하는 $O(logM)$ 이다.

struct Node
{
    ll a, b;
    Node *lc, *rc;
    Node() : a(0), b(INF), lc(NULL), rc(NULL) {}
};

void update(Node *node, int tl, int tr, ll a, ll b)
{
    int mid=tl+tr>>1;
    ll fl=node->a*tl+node->b, fr=node->a*tr+node->b;
    ll nfl=a*tl+b, nfr=a*tr+b;

    if(fl>=nfl && fr>=nfr) { node->a=a; node->b=b; return; }
    if(fl<=nfl && fr<=nfr) return;
    if(node->lc==NULL) node->lc=new Node();
    if(node->rc==NULL) node->rc=new Node();
    update(node->lc, tl, mid, a, b);
    update(node->rc, mid+1, tr, a, b);
}

ll query(Node *node, int tl, int tr, int pos)
{
    if(node==NULL) return INF;
    int mid=tl+tr>>1;
    ll now=node->a*pos+node->b;
    if(pos<=mid) return min(now, query(node->lc, tl, mid, pos));
    else return min(now, query(node->rc, mid+1, tr, pos));
}

Node *root=new Node();

 

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

https://oj.uz/problem/view/CEOI17_building