알고리즘 공부방

Li Chao Tree는 일차함수들의 볼록 껍질을 관리하는 자료 구조로, 기울기가 단조성을 보이지 않는 경우의 CHT 문제들을 해결하기 위하여 사용된다. https://cp-algorithms.com/geometry/convex_hull_trick.html 기본적인 꼴은 segment tree와 동일하다. 각 노드에는 그 노드의 구간을 담당하는 직선이 하나씩 있는데, 이때 주의할 점이 이 구간에서 이 직선이 항상 최대라는 것이 아니라 최댓값 후보 직선들 중 하나라는 것이다. 업데이트는 그 구간에 이미 들어 있던 직선과 지금 직선의 양 끝 부분의 함숫값을 비교한다. 만약 함숫값이 어느 하나가 양쪽 모두 크다면, 전체 구간에서 다 큰 것이기 때문에, 유지하던가, 갱신한다. 하지만 그것이 아니라면 원래 있던 ..

Convex Hull Trick은 DP의 시간 복잡도를 획기적으로 줄일 수 있는 방법으로, DP optimization의 세가지 종류 중 하나이다. CHT조아 $dp(i) = min_{j