In the problem Min Segments, we used the sliding window technique to efficiently compute the minimum value in each M-length segment of an array, for a fixed value of M.
Suppose, instead, we want to efficiently compute the minimum for arbitrary intervals (i,j) in the array. This is the simplest form of a class of problems called range queries. More complex versions of the problem allow the data in the array to be updated dynamically, between queries. In such cases, it is not sufficient to pre-process the array and maintain static information about its contents, since the contents keep changing.
In this section, we examine range-query problems with increasing levels of complexity and introduce some clever data structures that can be used to efficiently process such queries.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky