Segment Tree - kth (1) 썸네일형 리스트형 160. Segment Tree - kth 세그먼트 트리에서 $k$번째 원소를 빠르게 찾는 방법에 대해 알아본다. 다음과 같은 쿼리가 $q$개 주어지는 문제를 생각해 보자. $1\ k$: 집합에 원소 $k$를 추가한다. $k$는 $1$ 이상 $n$ 이하의 정수 중 하나이다. $2\ k$: 집합에서 $k$번째로 작은 원소를 출력한다. 이 문제를 해결하는 가장 간단한 방법은 $1$번 쿼리에서 추가되는 원소를 정렬된 집합에 끼워넣는 방법과 $2$번 쿼리마다 집합을 정렬하는 방법이지만 두 방법 모두 쿼리 하나를 처리하는 시간이 $\Omega(n)$이 돼서 전체 시간복잡도는 $\Omega(nq)$로 표기할 수 있다. 물론 $n$과 $q$가 크면 속도가 너무 느려진다. 세그먼트 트리는 이 문제를 $\Theta(q \lg n)$에 해결하는 방법을 제공한다. .. 이전 1 다음
