본문 바로가기

알고리즘

Order Statistic Tree

 

GitHub - hijkl2e/problem_solving: 알고리즘 문제 해결

알고리즘 문제 해결. Contribute to hijkl2e/problem_solving development by creating an account on GitHub.

github.com

요약

Order Statistic Tree(이하 pbds)는 다음 연산을 O(logN)에 처리할 수 있다. 다만 상수가 조금 크다.

  • K번째 원소 찾기
  • 주어진 원소의 순서 구하기

위의 연산이 필요하면 일단 pbds를 들이대보자.

TLE가 발생하면 좌표 압축 + Fenwick Tree로 처리하자.

 

연습 문제

1. Cookie Selection

pair<int, int> pbds

2. Galactic Collegiate Programming Contest

tuple<int, int, int> pbds

3. Baby Names

string pbds

 

'알고리즘' 카테고리의 다른 글

Euler's phi function  (0) 2022.10.05
Union-Find  (0) 2022.10.04
Fenwick Tree  (0) 2022.09.30
Knuth's Optimization  (0) 2022.09.28
유클리드 알고리즘 관련 정리  (0) 2022.09.26