Tree/LogN Min Search

Skeina, The Algorithm Design Manual, Chapter 3

Question

Problem 3-11: Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer questions of the form: given i, given j, find the samllest value in xi, ..., xj.

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

For part a = use a hash table. We pass it every combination of (i,j) and save the minimum value as a value. Ues O(N^2) space, O(1) time.

Part b

I puzzled over part b fora long while. [This wiki](http://www.algorist.com/algowiki/index.php/TADM2E_3.11) gives one possible solution. A bit tricky, and even the solution takes some puzzling over.

Implement a binary tree - each tree node will hold the lowest value for a particular range of indices.

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.

Lowest value in 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