Exercise 10.6

Let I be a set of intervals on the real line. We want to be able to count the number of intervals containing a query point in O(log n) time. Thus, the query time must be independent of the number of segments containing the query point.

• Describe a data structure for this problem based on segment trees, which uses only O(n) storage. Analyze the preprocessing time, and the query time of the data structure.
• Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
• Describe a data structure for this problem based on a simple binary search tree. Your structure should have O(n) storage and O(log n) query time. (Hence, segment trees are actually not needed to solve this problem efficiently.)