-
Static Range Minimum QueriesCSES 2023. 12. 7. 16:08
방법 1 - Segment tree
Build a Range minimum query segment tree in O(N) time and answer each query in O(logN).
방법 2 - Sparse Table
Sparse Table - Algorithms for Competitive Programming
Sparse Table Sparse Table is a data structure, that allows answering range queries. It can answer most range queries in $O(\log n)$, but its true power is answering range minimum queries (or equivalent range maximum queries). For those queries it can compu
cp-algorithms.com
Build a sparse table in O(NlogN) time and answer each query in O(1).
'CSES' 카테고리의 다른 글
문제&editorial 링크(editorial은 구글링도 해볼 것) (0) 2023.12.07