Range Tree
A BST on one coordinate with a secondary structure per node for orthogonal range queries.
Interval, kd and Range Trees: Range tree: canonical subtrees answer in y
Right boundary at 12, inside the x range, so its left subtree at 10 hangs towards the range. Its subtree is entirely inside 5-13 in x, so it is a canonical subtree: its sorted y values are 15, and 0 of them lie in 4-12, found by binary search. Running total 3.
Cost
- Build
- O(n log n)
- Query
- O(log^2 n + k)
- Space
- O(n log n)
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.