1. (20 points) Let A[1..n] be an array that stores n possibly non-distinct numbers. (a) (10...

Transcribed Image Text:

1. (20 points) Let A[1..n] be an array that stores n possibly non-distinct numbers. (a) (10 points) A range query specifies two integers à and y that form an interval (x, y]. The answer to a range query is the number of elements in A that are greater than x and less than or equal to y. There is NO requirement that x and y are elements of A. As an example if A = [4, 5, 2, 6, 8, 3, 4, 4], the range query for the interval (3, 6] would return 5 because there are five elements in A that lie in (3,6], namely A[1], A[2], A[4], A[7], and A[8]. Similarly, the range query for the interval (7, 10] would return 1. Describe an algorithm that generates a data structure C such that uses O(n) space and you can use C to answer any range query in O(log n) time. Explain the running time of your algorithm for constructing C. Describe in detail how you use C to answer a range query and explain why it takes O(logn) time. (b) (10 points) Suppose that the numbers in A[1..n] come from the range [1..k] for some positive integer k given to you. A range-sum query specifies two integers x and y in the range [1, k] that form an interval (x, y]. The answer to a range-sum query is the sum of elements in A that are greater thanx and less than or equal to y. As an example if k = 9 and A = [4, 5, 2, 6, 8, 3, 4, 4], the range-sum query for the interval (3, 6] would return 23 . The interval (7, 10] does not define a range-sum query because 10 is outside the range [1,9]. Describe in detail how you would organize the data structure C and con- struct C so that each range-sum query can be answered in O(1) time. Explain the running time of your algorithm for constructing C. Explain why a range-sum query can be answered in O(1) time. 1. (20 points) Let A[1..n] be an array that stores n possibly non-distinct numbers. (a) (10 points) A range query specifies two integers à and y that form an interval (x, y]. The answer to a range query is the number of elements in A that are greater than x and less than or equal to y. There is NO requirement that x and y are elements of A. As an example if A = [4, 5, 2, 6, 8, 3, 4, 4], the range query for the interval (3, 6] would return 5 because there are five elements in A that lie in (3,6], namely A[1], A[2], A[4], A[7], and A[8]. Similarly, the range query for the interval (7, 10] would return 1. Describe an algorithm that generates a data structure C such that uses O(n) space and you can use C to answer any range query in O(log n) time. Explain the running time of your algorithm for constructing C. Describe in detail how you use C to answer a range query and explain why it takes O(logn) time. (b) (10 points) Suppose that the numbers in A[1..n] come from the range [1..k] for some positive integer k given to you. A range-sum query specifies two integers x and y in the range [1, k] that form an interval (x, y]. The answer to a range-sum query is the sum of elements in A that are greater thanx and less than or equal to y. As an example if k = 9 and A = [4, 5, 2, 6, 8, 3, 4, 4], the range-sum query for the interval (3, 6] would return 23 . The interval (7, 10] does not define a range-sum query because 10 is outside the range [1,9]. Describe in detail how you would organize the data structure C and con- struct C so that each range-sum query can be answered in O(1) time. Explain the running time of your algorithm for constructing C. Explain why a range-sum query can be answered in O(1) time.

Answer rating: 100% (QA)

a To generate a data structure C for the range query you can use a binary search tree BST augmented ... View the full answer