우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,
이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다.
이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다.
1. 배열+sort
2. k번째 원소 세그먼트트리
3. k번째 원소 BIT
4. BIT + 파라메트릭서치 + 바이너리서치
5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치
6. 2D 세그먼트트리
어렵다.. 이름만 들어도 어렵네 @,.@
5번은 BOJ 7469번 가 대표적인 문제이다.
http://blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221341875102
1번은 일단 단순히 M개의 원소를 벡터에 넣고 정렬하여 A[k-1]로 구하는 방법으로 딱, 이 경우만 사용한다.
다른 경우는 시간 복잡도상 Time Out.
2,3번은 한번의 쿼리로 k 번째 수를 찾아 내려가는 것인데, 매 노드마다 왼쪽 구간에 존재하는 수와
오른쪽 구간에 존재하는 수를 검사하여 어느방향으로 가야할지를 결정하면서 리프노드까지 가는 것이다.
(실제 원소들의 값이 매우 클때 에는 좌표압축을 하기 때문에 수의 수의 가짓수가 O(n) 개라고 하겠다)
사실 시간복잡도는 2,3번은 O(nlgn)이며, 4번이 O(nlg^2n) 로 가장 느려야되는데
BIT가 워낙 빨라서 그런지 3번보다 4번이 더 빠르다. 하지만 update 함수를 비재귀(인덱스트리)로 작성하면
3번이 4번보다 빠르다.
+추가적으로 이 문제를 5번 방법으로 풀 때의 코드를 올린다. 하지만 이 문제의 제약에서는 시간안에 돌지않는다.
복잡도가 무려 O(nlgn + nlg^3n) 이기 때문이다. 하지만 구간의 정보에 대한 쿼리가 주어지는 문제에서는
앞에서 말했듯 2,3,4번은 못쓰고 이 방법을 써야 할 것이다.
참조: https://sgc109.tistory.com/127 [PS와 개발을 공부하자]