a a Problem 7 (10%). Let S be a set of n integers. Given a value q, a half-range query reports all the numbers in S that

[answerhappygod]

A A Problem 7 10 Let S Be A Set Of N Integers Given A Value Q A Half Range Query Reports All The Numbers In S That 1 (242.87 KiB) Viewed 37 times

a a Problem 7 (10%). Let S be a set of n integers. Given a value q, a half-range query reports all the numbers in S that are at most q. Describe a data structure on S that can answer any half-range query in 0(1+k) time, where k is the number of integers reported. Your structure must consume O(n) space. For example, consider S = {20, 35, 10, 60, 75,5, 80,51}. A query with q = 15 reports 5, 10.