Exercises
-
Exercises 10.2, 10.5, 10.6(a), 10.9, 10.10.
Exercises 10.2 and 10.5 are the hardest. So, also consider the other problems even if these first two problems cause you some difficulties. In 10.2, you do not need to build a priority search tree which looks exactly like the structure built using the normal construction method. You should just build something with the same asymptotic properties.
-
Preprocess a set S of n intervals
so that the following type of queries
can be answered efficiently. A query consists of an interval
qI = [qx:qy] and an element
qe∈qI.
One must report all intervals from S
that are contained in qI and contain
qe.
- Consider which problem arise if you want to make segment trees dynamic. It would be nice, for instance, if it was possible to (efficiently) insert an additional interval into the structure and then have the same guarantees on the search and report time after that. It is not presented as a dynamic structure in the textbook, so there will probably be a problem somewhere. Find it!