개요Cartesian Tree는 주어진 수열을 기반으로 구성되는 이진 탐색 트리 구조로, 배열의 순서와 값의 최소(또는 최대) 조건을 동시에 만족하는 이진 트리다. 이는 RMQ(Range Minimum Query), LCA(Lowest Common Ancestor) 등 다양한 알고리즘 문제의 전처리 단계에서 유용하게 사용된다.1. 개념 및 정의Cartesian Tree는 다음 두 가지 성질을 모두 만족하는 트리다:이진 탐색 트리(Binary Search Tree): 노드의 중위 순회가 원래 수열과 일치해야 함힙 속성(Min-Heap 또는 Max-Heap): 부모 노드의 값이 자식보다 작거나 커야 함목적: 값 기반 정렬과 순서 기반 조회를 동시에 처리필요성: RMQ와 같은 문제에서 빠른 질의 처리를 위한 ..
