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 [email protected].
