[PS를 위한 자료구조 10강] 펜윅 트리로 머지 소트 트리 구현하기

PS를 위한 자료구조 10강

# 펜윅 트리를 이용한 머지 소트 트리 # 에 대해 알아보겠습니다.

펜윅 트리로도 머지 소트 트리를 구현할 수 있습니다. 

펜윅 트리의 치명적 단점에 대해 전달드렸듯이, 

펜윅 트리는 [1, R] 구간의 쿼리만 처리가 가능합니다.
따라서 제한적 상황에서만 사용할 수 있습니다.

[수열과 쿼리1]
https://www.acmicpc.net/problem/13537

하지만 이 문제에서는 사용할 수 있습니다.
[1, R] 구간의 K보다 큰 수 - [1, L-1] 구간의 K보다 큰 수 = [L, R] 구간의 K보다 큰 수
가 성립하기 때문이죠.


구현은 다음과 같습니다.
i번 노드에 i&-i개의 자료가 정렬이 되어있으면 됩니다. 
다만 세그먼트 트리로서 이용할 때와는 달리 자료를 직접 정렬해주어야합니다.
펜윅트리는 두 자식간의 결합으로 노드를 완성할 수 없기 때문이죠.

따라서 이번에는 다른 테크닉을 이용하지 않고, 약간 무식하게 머지 소트 트리를 구성하겠습니다.

배열 수열[N]
배열 펜윅[N+1]
for i in 1 to N:
    펜윅[i] = 정렬(수열[i-(i&-i) .. i-1])
    # (i&-i)개의 수열을 가져와 정렬​

이렇게 하는 것이 가장 마음이 편합니다.
왼쪽 자식만큼은 이용할수도 있겠으나, 정신건강을 위해서는 그냥 위와 같이 해줍시다.

시간복잡도는 제가 한 번에 표현할 수 있는 방법을 잘 모르겠습니다.

 혹시 아시는 분은 댓글 부탁드립니다.
확실하게 말씀드릴 수 있는 것은, 1log1 + 2log2 + 4log4 + ... + NlogN이 등장하므로 

NlogN보다는 크면서 N^2보다는 훨씬 작을 것이라고 예상할 수 있습니다.

쿼리 함수는 앞선 펜윅 트리 강의에서 했던 것 처럼 응용하면 될 것 같습니다.

이번 글은 제가 썼던 글 중 가장 짧게 마무리가 되었네요. ㅎㅎ

머지 소트 트리를 사용해야하는 문제 중, 펜윅 트리를 이용하여 해결할 수 있는 문제가 있을 겁니다. 
여러분들이 직접 해결해보시기 바랄게요..!

정답코드입니다.
[c++]
http://boj.kr/580fafae98754e96b26c152ef81ded39

[파이썬]
http://boj.kr/c0c8feb0aaa540bb85a51a49f1c13084