Tree/LogN Min Search

Skeina, The Algorithm Design Manual, Chapter 3

Problem 3-11

Problem 3-11: Suppose we're given a sequence of values $x_{1},x_{2},\dots ,x_{n}$

Now suppose we seek to quickly answer questions of the form: given $i,j$, find the smallest value in the subsequence $x_{i},\dots ,x_{j}$.

Part a - design a data structure using $O(N^{2})$ space, answering queries in $O(1)$ time.

Part b - design a data structure using $O(N)$ space, $O(\log N)$ time.

Part a

Part A: using $O(N^{2})$ storage space means we do pairwise pre-processing of our values.

The solution here is to use a hash table. During pre-processing we iterate over all $N^{2}$ combinations (i,j) and compute the minimum value for each and store it.

Uses $O(N^{2})$ space, $O(1)$ time.

Part b

Part b had me stumped for a while.

We want a data structure using $O(N)$ space, and we want lookups to take $O(\log N)$ time.

The Algorist wiki (link) gives one possible solution, but that's a bit tricky. Even the solution takes some puzzling over.

The solution involves log lookup time, so it must be a tree. One tree node per array element.

The tree data structure should look something like a min heap, where a node higher on the tree indicates a "more global" minimum. That is, each node represents a particular range of indices, and the higher on the tree a node is, the larger the range of indices it covers.

O(N) Space:

Each node stores a single minimum value that represents the minimum in that range. Constant space for each node means O(N) space is achieved.

O(lg N) lookups:

The root node represents the range of the entire input sequence. It stores the global minimum.

The root node's children span the left and right halves of the input sequence. Similar to a binary search, each level in the tree cuts the array size in half.

Each leaf spans a single element range of input, so there are lg N levels in the tree. (N = number of items in our array) If there is a single node, the minimum for that one-element span is the value of that element.

Total O(N) nodes in tree.

Algorithm:

• Query function is recursive, and passes the query (which has a low and high value), starting from the root
• If the query range matches the current node's range, return the current node's value
• If the query range is entirely within the left/right hand side (query.low > node.low && query.high < node.high), return the result of calling query on left/right hand node
• Otherwise return lowest results from calling query on LH and on RH (minimum of two, only checking query.low > node.low or query.high < node.high)
• Query visits maximum of 2 leaf nodes