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. -Thanks Bujji -- 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].
