ps:order_statistic_tree
Order Statistic Tree
- 처음에는 이런 용어가 따로 있는지를 몰랐다. 그래서 적당히 Ordered Set이라는 타이틀로 페이지를 만들었는데, 위키피디아에서 https://en.wikipedia.org/wiki/Order_statistic_tree 문서를 발견하고 타이틀을 바꿨다.
- 사실 정확하게 의미가 매치되는 것은 아니다. 위키의 설명에서는 바이너리 서치 트리에 추가적으로 Select(k번째로 작은 원소 찾기)와 rank(x보다 작은 원소의 갯수 찾기, 다시말하면 정렬했을때 X의 index찾기) 연산을 지원하는 자료구조 라고 정의되어 있다. 내가 의미한 것도 필요로 하는 기능면에서는 일치하지만, 꼭 바이너리 서치 트리일 필요는 없다.
- 즉, 내가 의도한 바는 대충 삽입/삭제/특정 원소 찾기/Select/Rank 를 로그 시간에 해줄 수 있는 자료 구조이다.
- 기본적으로 이러한 연산들은 Binary Search Tree가 지원하는 연산들이다. 정확히는 Balanced Binary Search Tree (BBST).
- 수업시간에 대표적으로 배우는 BBST에는 AVL tree, Red-black tree 등이 있으나, 손으로 짜기에는 코드양이 꽤나 많고 그래서 PS용으로 쓰기는 좀 어렵다는 문제점이 있다.
- 사실 c++에서는 std::set 이 표준 라이브러리에 존재하고, 삽입/삭제/찾기 등을 O(logn)에 처리해준다. 구현은 거의 Red-black tree로 구현되어있다고 보면 된다. 그러나, 이렇게 red-black tree의 구현체가 라이브러리에 있음에도, 이 라이브러리는 k번째로 작은 원소 찾기/X보다 작은 원소의 갯수 찾기를 지원해주지 않는다. 그리고 삽입/삭제/찾기만 원한다면 그냥 해시테이블(std:unordered_set)을 쓰는게 더 효율적이다.
- 물론, std::set는 lower/upper_bound 함수와 O(n)시간의 이터레이션을 지원하기 때문에 std:unordered_set과 다른 효율성이 있기는 하다.
- 그래서 GNU c++에서는 c++표준에는 없지만, 자체적으로 저런 연산을 지원하는 데이터 구조를 제공한다.
- find_by_order와 order_of_key 메소드를 지원. 내부 구현은 RB tree, splay tree, ordered vec을 선택 가능하나 RB tree가 가장 빠르다.
- 그래서 GNU c++을 쓰면 저것들을 바로 사용 가능하다..
- 하지만 우리의 Python에는 저런 라이브러리가 없기 때문에, 직접 구현해야 한다.
- 앞에서도 말했듯이 대표적인 BBST인 RB tree나 AVL tree는 너무 구현량이 많다. 그래서 보통 BBST를 심플하게 손으로 구현해야 할 경우에는 보통 Splay tree나 Treap를 사용한다. 이것을 직접 구현해서 쓰는 방법도 가능하다.
- Python의 경우에는 또 다른 선택지가 있다. 파이썬의 외부 라이브러리중에서 유명한 것으로 Sorted Containers라는 것이 있다. 처음 말한 Ordered Set의 기능을 구현한 컨테이너인데, 성능 측정 결과에 따르면, C확장을 사용해 구현한 RB tree, AVL tree, treap 등등보다 속도가 빠르다고 한다. 성능에 비해 구조는 비교적 간단하다. 최대길이 1000짜리 리스트들을 리프 노드로 갖는 트리 구조이고, 리프노드에 도착하면 거기에서는 바이너리서치를 거쳐서 원소에 접근하는 방식이다. 그래서 소스 코드도 주석들을 제외하면 그렇게까지 크지는 않다. 잘 다듬어서 PS용으로 사용하는 것도 가능하다.
- 하지만, 사실상 이게 본론인데, 구간 합 세그먼트 트리를 이 용도로 사용하는 것도 가능하다. 그리고 많은 경우에 이것이 가장 효율적이다. 자세한 내용은 아래 참고.
- 실제로 BOJ에서도 이런 연산을 요구하는 문제에는 '세그먼트 트리'가 태그로 붙어있다.
- 결론을 3줄 요약하면.
- 인풋이 몇백만 이하의 자연수라면, 세그먼트트리/펜윅트리 기반의 구현을 사용한다.
- 아무거나 써도 비슷하긴 하지만, kth()가 주로 필요하면 세그먼트트리, count_less_than()이 주로 필요하면 펜윅트리를 사용하는게 좀더 효율적.
- 인풋이 그보다 큰 범위의 자연수라면, 구간압축 + 세그먼트트리/펜윅트리를 사용한다
- 인풋이 자연수 범위가 아니라면, 역시 구간압축 + 세그먼트트리/펜윅트리를 사용한다
- 오프라인 쿼리로 처리하는 것이 불가능하다면, 다이나믹 세그먼트 트리 기반의 구현 또는 treap을 사용한다.
- 둘다 아직 구현을 안해봐서 뭐가 더 빠른지 모른다. 이후 추가예정
- 속도를 최대한 쥐어짜서 향상시켜야 한다면, Sorted Containers도 사용해본다. (더 빨라질지 아닐지는 모름)
세그먼트 트리에 기반한 구현
- 저장할 값들이 [0, N) 사이의 정수만으로 되어있다고 생각하면. 그냥 size가 N인 구간합 세그먼트 트리를 이러한 용도로 사용할 수 있다.
- 크기가 N인 배열 A로부터 세그먼트 트리를 만들었다고 하자. BBST에서 O(logM) 에 처리되던 연산들을 어떻게 할 수 있는지 보자. (M은 컨테이너에 저장된 원소의 갯수)
- BBST에 X를 삽입하거나 삭제하는 것은 A[X]에 1을 더하거나 빼는 것과 같다. 이것은 O(logN)
- BBST에서 X보다 작은 원소의 갯수를 찾는 것은, sum(A[0:X]), 즉 구간합을 구하는 것과 동일하다. 이것도 O(logN)
- BBST에서 k번째로 작은 원소를 찾는 것도, 세그먼트 트리를 루트노드에서부터 양쪽 차일드 노드의 구간합들을 비교해 나가면서 서치하는 것으로 O(logN)에 구현할수 있다.
- 결국 BBST에서는 O(logM)에 가능했던 우리가 원하던 모든 연산들이, 세그트리를 사용해도 O(logN)에 해결 가능하다!
- 이게 비교 기반으로 구현된게 아니라서 꼼수같은 느낌이 들기는 하는데, 소팅 알고리즘과 비슷하게 생각할 수도 있다. 소팅을 할때도 비교기반의 bubble/merge/quick/heap sort대신에, 카운팅 기반의 bucket/radix sort가 존재하고 데이터 타입이 특정한 경우에는 이쪽이 더 효율적이다.
- 이 방법의 장점은 이런것들이다
- 다른 BBST를 짜는 것보다 코드가 짧다. (GNU C++은 그냥 pb_ds를 인클루드해서 쓰면 되니 해당 안됨..)
- N과 M이 비슷하다면, 상수항이 더 작아서, 속도도 빠르다.
- 반면 단점은 이런것들이 있다.
- 키가 자연수가 아닌 경우 추가적인 처리 없이는 불가능
- N이 M보다 훨씬 클 경우, 속도가 느리고, 메모리도 많이 먹는다.
- 하지만 이 두가지 단점은 동일한 방법으로 극복 가능하다.
- 오프라인 쿼리가 가능한 경우, 쿼리에 등장하는 키값들을 모아서 정렬함으로써, 자연수로 매핑시킬수 있다 (좌표압축과 같은 아이디어이다).
- 이 방식으로 키가 자연수가 아닌 경우를 처리할 수 있다. O(QlogQ)의 전처리 시간이 추가로 필요하지만, 그것을 포함해도 보통은 이 편이 속도가 더 빠르다
- 키가 이미 자연수인 경우에도, 속도 단축을 하기 위해서 좌표 압축을 쓰는 것은 좀 고려해볼 필요가 있다. O(QlogN) 이 O(QlogQ)가 되기는 하는데, N과 Q가 로그 스케일로 들어가기 때문에 Q가 N보다 몇십배 큰 정도로는 실제 속도는 별로 차이가 안난다. 키가 자연수인 경우에도 좌표 압축을 써야 하는 경우는 메모리가 터지는 것 때문인 경우가 더 많다.
- 오프라인 쿼리가 아닐경우에는 좌표 압축을 쓸수 없다. 다만 키값들을 범위가 크지만 자연수로 바로 매핑 가능한 경우에는 다이나믹 세그먼트 트리를 써서 할수는 있을것 같다. 다만 이 경우에도 Treap 등을 구현해서 쓰는것보다 빠른지는 확인 안해봤다. TODO
- 세그먼트 트리만 계속 언급했는데. 구간합이므로, 펜윅 트리로도 똑같이 구현이 가능하다. 삽입/삭제/X보다 작은 원소의 수는 똑같은 연산과정으로 처리가 가능하다. kth-element는 직접 구현해줘야 한다. 검색하다 발견한 몇몇 자료에서는 이것을 이진탐색을 사용해서 O(log^2(N))에 구현하는 방법만 소개하고 있는데, 조금만 생각해도 충분히 O(logN)에 구현할수 있다는 것을 알 수 있다.
- 그러나, 이렇게 펜윅트리에서의 kth-element 함수를 O(logN)으로 구현하더라도 bottom-up 세그먼트 트리를 사용하는 것보다 다소 느렸다. 일반적인 작업에서는 펜윅 트리가 구간합 세그먼트 트리보다 빠르지만, 이 함수만을 놓고 볼 때에는 그런 메리트가 없다.
- 펜윅 트리의 kth 구현
def kth(self, k: int) -> int: pos = 0 for i in range(self._size.bit_length() - 1, -1, -1): p = (1 << i) if pos + p - 1 < self._size: v = self._tree[pos + p - 1] if v < k: k -= v pos += p return pos
- 세그먼트 트리의 kth 구현
def kth(self, k: int) -> int: i = 1 while i < self._size: i += i t = self._tree[i] if t < k: k -= t i += 1 return i - self._size
- 줄 세우기문제 (Q≤100,000) 에서는 세그트리 버전으로 864ms, 펜윅트리 버전으로 1124ms가 나왔다.
- 데이터 구조문제 (Q≤2,000,000) 에서 PyPy로 제출했을때 세그트리 버전으로는 2870ms, 펜윅트리 버전으로는 3136ms가 나왔다.
- Sorted Containers을 사용한 코드는 2316ms가 나왔다.
- 하지만 count_less_than()의 경우는 여전히 펜윅트리 구현이 세그트리 버전보다 빠르다
- 여우가 정보섬에 올라온 이유문제에서는 세그트리 버전으로 2032ms, 펜윅트리 버전으로 1700ms가 나왔다.
- 따라서 결론적으로는 kth를 쓸 경우는 세그먼트트리 구현을, count_less_than을 쓸 경우는 펜윅트리 구현을 쓰는 편이 약간 더 효율적이지만, 귀찮으면 아무거나 쓰자. 두 버전 모두 Teferi library에 구현해 두었다.
upper_bound / lower_bound
- cpp 에서는 upper_bound, lower_bound 는 기본 set/map을 이용해서 O(logn)에 처리 가능하다. rank와 k-th 가 안돼서 pb_ds를 쓰는 것뿐.
- python에서는 upper_bound, lower_bound 를 지원하는 트리맵 구조도 기본적으로 지원되지 않기 때문에 만들어야 한다. 하지만 Order Statistic Tree를 만들었다면, rank과 k-th로부터 upper_bound, lower_bound를 처리할 수 있다.
- lower_bound, 즉 key보다 크거나 같은 원소중 가장 작은 원소를 찾아내는 것은, 먼저 rank쿼리를 통해서 key보다 작은 원소의 갯수 K를 구한 다음, select쿼리로 K+1번째 원소를 가져오면 된다.
- upper_bound, 즉 key보다 작거나 같은 원소중에서 가장 큰 원소를 찾아내는 것은, 역시 먼저 rank 쿼리를 통해서 (key+1)보다 작은 원소의 갯수 K를 구한다음, select쿼리로 K번째 원소를 가져오면 된다.
- [beg, end) 범위의 원소들을 추출하는 것은 이런식으로 하면 된다
def get_nums_between(ost, beg, end): k = ost.count_less_than(beg) ret = [] for i in range(k + 1, ost.size() + 1): nums = ost.kth(i) if nums >= end: break ret.append(nums) return ret
- 물론 이렇게 쿼리를 두번 거쳐서 계산하는것보다, 그냥 한번 탐색하면서 찾을 수 있도록 그냥 구현할수도 있다.. 하지만 사용할 일이 많지 않아서, library에 만들어두지는 않았다.
- 관련 문제: 장애물 경기
ps/order_statistic_tree.txt · 마지막으로 수정됨: 2022/10/13 07:19 저자 teferi
토론