테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 구간 쿼리 문제 ======
 
  * 필요한 자료구조나 트릭에 대한 설명은 다른 페이지로 모아놓고, 여기에서는 쿼리 종류별로 어떻게 처리해야 할지에 대한 치트시트 비슷한 것을 만드려고 한다
    * (X) 자료구조에 대한 설명 => 이 자료구조로 해결할수 있는 쿼리 유형들   (보통 이렇게 설명하는데)
    * (O) 쿼리 유형에 대한 설명 => 이 쿼리를 해결 가능한 자료구조들    (여기에서는 이런식으로)


===== No update / Range Min =====
  * offline query로 푸는게 속도는 가장 빠르다
    * disjoint set을 명시적으로 이용하는 arpa's trick 보다, 시복은 나쁘지만 그냥 stack과 bisect를 이용하는 방법이 더 빠른거 같았다
    * [[ps:problems:boj:2357]] [기본]
    * [[ps:problems:boj:6213]] [기본]
  * 쿼리들이 슬라이딩 윈도우에 대해 주어진다면, deque 트릭을 사용하는게 더 빠르..려나? 안해봄


===== Point Set / Range Min =====


===== Range Set / Range Min =====


===== Point Set / Range Sum =====
  * Point Add 그냥 원래 배열의 값들을 따로 저장해놓고 있으면 point set으로 처리 가능하다
    * 구현상으로는 point add가 point set보다 더 쉽지만, 일반화를 위해서 point set을 제공하자.
  * {{myicon>g1}} [[ps:problems:boj:11143]]

===== Range Add / Range Sum =====
  * Fenwick tree 두개 사용
  * Lazy segment tree

===== Range Add / Range Min =====
  * Lazy segment tree
  * {{myicon>p3}} [[ps:problems:boj:8330]]

===== No update / batch Range Rank =====
  * Order Statistic Tree + Offline query technique
  * [[ps:problems:boj:23400]]

===== No update / Range Rank =====
  * Merge Sort Tree
  * [[ps:problems:boj:13544]]

===== No update / Range K-th =====
  * Index-based Merge Sort Tree
  * Persistent Segment Tree
  * [[ps:problems:boj:7469]]
  *