Sparse Table ~ Ankur's Blog

Sparse Table

Ankur's BlogJuly 03, 2019 No comments

Note: 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 compute the answer in $O (1)$ time.

The only drawback of this data structure is, that it can only be used on immutable arrays. This means, that the array cannot be changed between two queries. If any element in the array changes, the complete data structure has to be recomputed.

Rsources:

Tanvir's Blog

E-maxx

GeeksForGeeks

HackerEarth

Tushar Roy Video

Topcoder

Codechef

adilet.org_blog_sparse-table

Implementation: according to (This ) problem

No comments:

Post a Comment