On Wednesday, July 23, 2014 8:41:33 AM UTC-4, bujji wrote: > > Suppose that we are given a sequence of n values x1, x2, ..., xn and seek > to > quickly answer repeated queries of the form: given i and j, find the > smallest value > in xi, . . . , xj . > > Design a data structure that uses O(n) space and answers queries in O(log > n) > time. For partial credit, your data structure can use O(n log n) space and > have > O(log n) query time. > > You can use a segment tree representing the range 1..n. Each tree node stores the sequence index of the minimum element in the represented segment. Querying this structure for a range i..j is just finding all the nodes that represent included subranges and taking the min. How many can that be? It is easy to show that a recursive search from the root will have to look at most two nodes per tree level. Therefore the query is O(2 log n) = O(log n). The tree is best represented in a simple array, since it is nearly complete like an array-based heap. This array will elements 2n-1 elements if n is a power of 2 or at most another factor of 2 if n is arbitrary, so space is clearly O(n).
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
