ITPE * JackerLab

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

개요Segment Tree(세그먼트 트리)는 배열 또는 수열에서 **특정 구간에 대한 질의(Query)와 갱신(Update)**를 효율적으로 수행하기 위한 이진 트리 기반의 고급 자료구조입니다. 구간 합, 최소값/최대값, 최빈값, 최대공약수(GCD) 등 다양한 집계 연산을 O(log n) 시간 내에 처리할 수 있어, 알고리즘 문제, 게임 서버, 실시간 분석 시스템 등에서 널리 사용됩니다.1. 개념 및 정의Segment Tree는 크기 n의 배열에 대해 다음과 같은 연산을 빠르게 수행할 수 있는 트리입니다:build(): 배열을 기반으로 트리 구성 (O(n))query(l, r): 구간 [l, r]에 대한 집계 결과 반환 (O(log n))update(i, v): i번째 요소를 v로 갱신 (O(log n)..