Li Chao Tree

나중에 까먹을 때를 대비한 기록용 포스팅

 

레퍼런스 : https://justicehui.github.io/hard-algorithm/2019/05/22/Li-Chao-Tree/

(설명도 쉽게쉽게 되어있어서 많이 도움되었습니다.)

 

 

핵심은 특정 구간에서 Line들의 lower(혹은 upper) hull을 관리할 수 있다는 것이다.

CHT 문제를 풀 때 사용할 수 있다.

 

+) 덤으로 Dynamic Segment Tree에 대한 개념도 공부하게 되었다.

필요 시에만 노드를 생성하며, 직선이 존재할 수 있는 범위가 $[s,e]$일 때 하나의 쿼리에 $O(log(e-s))$개의 노드만 추가된다.