제 코드랑 많이 비슷하네요!
위 코드를 통해 만들어지는 트리는 담당하는 구간을 소팅된 상태로 저장하는 세그먼트 트리입니다.
조악한 그림 죄송합니다.
위처럼 세그먼트 트리의 각 노드가 자신이 담당하는 구간을 정렬된 상태로 모두 저장하고 있습니다. 따라서 노드 하나는 정수 하나가 아니라 배열 하나로 표현됩니다.
공간복잡도가 O(nlogn)이 되며, 해당 문제에서는 일반적인 세그먼트 트리처럼 구간을 대표하는 노드들에서의 바이너리 서치를 통해
C 이하인 값이 K개 이상이 되는 최소의 C를 찾는 방식으로 K번째 수를 찾습니다.
zasxer 7년 전
소스 일부를 읽다가 궁금한 점이 있어 질문드립니다.
bt[i / 2].push_back(bt[i][i1++]);
bt[i][i1++]를 push_back하면 bt[i/2]에는 어떤 형식으로 들어가 있나요?
문제를 sqrt decomposition으로 풀었는데, segment tree를 활용하여
query를 보내고 받는 형식이던데 구동 방식이 어떻게 되나요?