머지소트트리2 [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개의 자료가 정렬이 되어있으면 됩니다. 다만 세그먼트 트리로서 이용할 때와는 달리 자료를 직접 정렬해.. 2022. 3. 25. [PS를 위한 자료구조 9강] 머지 소트 트리의 개념과 구현 PS를 위한 자료구조 1-9강 # 머지 소트 트리 # 에 대해 알아보겠습니다. 다음의 문제를 봅시다. [수열과 쿼리1] https://www.acmicpc.net/problem/13537 이 문제를 해결하기 위해 다음과 같은 자료구조를 생각하면 어떨까요? 우리가 흔히 합병 정렬(merge sort)를 하는 과정은 다음과 같습니다. 1 2 3 4 5 6 7 8 | | 1 4 6 8|2 3 5 7 | | | | 1 8|4 6|2 7|3 5 | | | | | | | | 1 8 6 4 7 2 3 5 // 아래에서 위 순서로 진행 그런데 이 모습.. 어쩐지 눈에 익지 않나요? 그렇죠. 우리가 지금까지 공부한게 뭡니까. 세그먼트 트리입니다. 루트에서부터 분할해 나가고, 리프 노드부터 두 노.. 2022. 3. 24. 이전 1 다음