Edit Question - KnowledgeHub

Title Body

I'm stumped by the following homework question for an algorithms class: Suppose that we are given a sequence of n values x 1 , x 2 ... x n , and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in x i ... x j Design a data structure that uses O(n) space and answers queries in O(log n) time. Firstly, I'm uncertain whether a sequence refers to a sorted set, or an unsorted set - but since it doesn't say otherwise I'll assume sequence means unsorted. So, I realize this obviously must involve a binary tree, if we're talking about O(log N) lookup time. So basically, I figure, you have a set S , and you insert each element in S into a binary tree. The problem is, the question basically wants me to come up with a way to answer queries where I'm given a range of indices into an unsorted set - and then determine the lowest value in that range in O(log N) time. How is that possible? Even if each number of the set is inserted into the tree, the best I can do is lookup any particular number in O(log N) time. This doesn't allow me to find the lowest value in an unsorted range of numbers in S . Any suggestions?

Tags (comma-separated) Cancel