TADM2E 3.11
1. Design a data structure that uses $ O(n^2) $ space and answers queries in $ O(1) $ time.
Build an $ n × n $ lookup table with the answer to every possible query, indexed by $ i $ and $ j $.
2. Design a data structure that uses $ O(n) $ space and answers queries in $ O(\log n) $ time.
The basic idea in this solution is to build a multi-resolution representation of the input, with each node able to answer the query for part of the input sequence. A tree of such nodes makes it possible to answer arbitrary queries quickly by covering the query range with ranges covered by nodes.
Build a binary tree in which each node holds the lowest value for a range of indexes. The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence, and so on. Each leaf node spans a single-element "range" of the input, with the "lowest" value in that range being the value at that position in the input sequence. The total number of nodes in the tree is $ O(n) $.
The query function is recursive, starting from the root:
- If the query range exactly matches the range spanned by the current node, return the current node's value.
- If the query range falls entirely within the left half, return the result of calling the query function on the left child.
- If the query range falls entirely within the right half, return the result of calling the query function on the right child.
- Otherwise return the lowest of the results from calling the query function on the left child and the right child.
The query function will visit at most two leaf nodes, and runs in $ O(\log n) $ time.
--Benw (talk) 18:08, 7 January 2015 (EST)
==== 2. (Alternate explanation)
We can assume, w.l.o.g., that n is a power of 2. For instance, if n is 16. We can then calculate minima for the following ranges:
- 0-15
- 0-7 and 8-15
- 0-3, 4-7, 8-11 and 12-15
- 0-1, 2-3, 4-5, 6-7, 8-9, 10-11, 12-13, 14-15
Note that this is O(n) space, or more precisely, (n-1) space. Now, to calculate the minimum for a particular range, build up non-overlapping ranges from the above set of ranges that cumulatively cover the desired range. If the range is 3-14, for example, the build-up would be 3; 4-7; 8-11; 12-13, and 14. This is O(log n). The minimum of the values of these ranges gives us the desired answer. To calculate the minimum of m unsorted values is O(m), and since m is O(log n), the minimum calculation is also O(log n).
