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.

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

Solution involves a log n term, so it must be a tree.

Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.

The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence. Etc.

Each leaf spans a single element range of input, meaning there are log(N) levels to the tree (where N is the number of indices in the array).

The lowest value in the range is the value at that position in the input sequence.

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