테페리넷

사용자 도구

사이트 도구

현재 위치: 테페리넷 » Problem Solving » 이론 » 구간 쿼리 문제
ps:이론:구간_쿼리_문제

목차

구간 쿼리 문제

  • 필요한 자료구조나 트릭에 대한 설명은 다른 페이지로 모아놓고, 여기에서는 쿼리 종류별로 어떻게 처리해야 할지에 대한 치트시트 비슷한 것을 만드려고 한다
    • (X) 자료구조에 대한 설명 ⇒ 이 자료구조로 해결할수 있는 쿼리 유형들 (보통 이렇게 설명하는데)
    • (O) 쿼리 유형에 대한 설명 ⇒ 이 쿼리를 해결 가능한 자료구조들 (여기에서는 이런식으로)

No update / Range Min

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

Point Set / Range Min

Range Set / Range Min

Point Set / Range Sum

  • Point Add 그냥 원래 배열의 값들을 따로 저장해놓고 있으면 point set으로 처리 가능하다
    • 구현상으로는 point add가 point set보다 더 쉽지만, 일반화를 위해서 point set을 제공하자.
  • 11143

Range Add / Range Sum

  • Fenwick tree 두개 사용
  • Lazy segment tree

Range Add / Range Min

  • Lazy segment tree
  • 8330

No update / batch Range Rank

  • Order Statistic Tree + Offline query technique
  • 23400

No update / Range Rank

No update / Range K-th

  • Index-based Merge Sort Tree
  • Persistent Segment Tree
  • K번째 수

토론

댓글을 입력하세요:
F᠎ Y F D K
 
ps/이론/구간_쿼리_문제.txt · 마지막으로 수정됨: 2026/04/01 09:02 저자 teferi