Segment Tree and Interval Tree

To build a Segment Tree, first sort all the end points of the segments, than adding -infinity and +infinity. For n segments, we then partition (-infinity, +infinity) into 2n+1 segments. These 2n+1 segments serve as elementary intervals. From them (considering them as leafs),  we can build a balanced binary tree. Then we add the n segments into the tree. Each node represents an interval. Non-leaf nodes represent the interval which is the union of their children. When adding a segment, we store the information of that segment in all nodes where the nodes' intervals are within the segment's interval. Besides, the nodes' parents' interval are not within the segment's interval.

• building cost is O(nlogn), space cost is O(nlogn), the cost to find all segments that contain a point (stabbing query) is O(k+logn)
• can also solve box overlap problem, Klee's measure problem.
• For multi-level segment tree, first build a base segment tree on one axis. Then build small segment tree on each node of the base tree, only for the segments stored on that node.
• For more details, please check http://www.cnblogs.com/TenosDoIt/p/3453089.html (in Chinese).

To build an Interval Tree, it is a little bit similar. First sort all the end points of the intervals and find the median points. Every node in the interval tree is associated with a point. And the node contains all the intervals that cover the point. The left child (sub-tree) of the node contains all the intervals whose upper bounds are smaller than the node's point. Similarly, we can define the right child.

• building cost is O(nlogn), space cost is O(n), the cost to find all intervals that overlap with an interval   (range query) is O(k+logn). 
• The result is a ternary tree with each node storing:
  • A center point
  • A pointer to another node containing all intervals completely to the left of the center point
  • A pointer to another node containing all intervals completely to the right of the center point
  • All intervals overlapping the center point sorted by their beginning point
  • All intervals overlapping the center point sorted by their ending point
• If we need to do a range query with interval tree, see we want to find the set of r that overlap with interval q. We first to sort all the start/end points of intervals, then find those have either start/end inside q. Second, we need select one point in q, do the query on the interval tree to find all the intervals that have the point. At the end, we need to merge results and do the dedup.

See Also: Klee's measure problem