Range Tree
A BST on one coordinate with a secondary structure per node for orthogonal range queries.
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.
What you will see
A 2D query decomposes into O(log n) canonical nodes, each answering in its own dimension.
Cost
| build | O(n log n) |
|---|---|
| query | O(log^2 n + k) |
| Space | O(n log n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.
Before this
Related
Taught by the same lesson
Interval, kd and Range Trees covers these too, in the same run.