From charlesreid1

Skeina, The Algorithm Design Manual, Chapter 3

Problem 3-11

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. Use O(N^2) space, O(1) time.

Part b

I puzzled over part b fora long while.

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

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

Flags