목차
구간 쿼리 문제
- 필요한 자료구조나 트릭에 대한 설명은 다른 페이지로 모아놓고, 여기에서는 쿼리 종류별로 어떻게 처리해야 할지에 대한 치트시트 비슷한 것을 만드려고 한다
- (X) 자료구조에 대한 설명 ⇒ 이 자료구조로 해결할수 있는 쿼리 유형들 (보통 이렇게 설명하는데)
- (O) 쿼리 유형에 대한 설명 ⇒ 이 쿼리를 해결 가능한 자료구조들 (여기에서는 이런식으로)
No update / Range Min
Point Set / Range Min
Range Set / Range Min
Point Set / Range Sum
- Point Add 그냥 원래 배열의 값들을 따로 저장해놓고 있으면 point set으로 처리 가능하다
- 구현상으로는 point add가 point set보다 더 쉽지만, 일반화를 위해서 point set을 제공하자.
Range Add / Range Sum
- Fenwick tree 두개 사용
- Lazy segment tree
Range Add / Range Min
- Lazy segment tree
No update / batch Range Rank
- Order Statistic Tree + Offline query technique
No update / Range Rank
- Merge Sort Tree
No update / Range K-th
- Index-based Merge Sort Tree
- Persistent Segment Tree