-
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(logn), 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