정윤성

Cartesian Tree를 활용한 문제 해결

Cartesian Tree Cartesian Tree는 대소 관계가 있는 값의 배열으로부터 유도되는 Binary Tree로, 구간의 min/max와 관련된 문제에 사용하면 편리한 자료 구조입니다. 배열의 최솟값 또는 최댓값에 해당하는 인덱스를 루트로 하게 되는데, Min Cartesian Tree의 경우 최솟값에 해당하는 $\mathrm{array}[i] = \min_{l \leq i \leq r}(\mathrm{array}[i])$인 $i$가 루트가 되며, $[l, r]$번째 원소의 최솟값에 대응되는 노드 $i$의 왼쪽 자손은 $[l, i-1]$에서의 최솟값, 오른쪽 자손은 $[i+1, r]$에서의 최솟값에 해당하는 인덱스가 됩니다. 자주 사용하게 되는 성질 몇 가지가 있는데, 각 노드의 subtree가...