There is a problem (10.6) in Computational Geometry: Algorithms and Applications 2.edition by de Berg et al. where you have to solve the problem of given $n$ intervals, $I$, on the real line, count the number of interval containing a query point $q$. There are several subproblems asking for efficient ways to do this using segment trees and a BST which I have solved, however sub question b asks:

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.

and for some reasons this seems much harder to me.

Any hints or help with how I can approach this would is appreciated. Note that this is indeed not homework, but the material on these topics are sparse online so I feel going through these exercises works.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.