| Invented by | Jon Louis Bentley, and independently several others (1979) | |
| Idea: |
- a search tree over points, built so that a whole rectangle can be answered by searching one coordinate at a time
- the main tree is a balanced search tree on x: the points sit in the leaves, and every internal node is one vertical line cutting the slab of the plane it owns in two
- on top of that, every node also carries all the points below it, sorted by y — its associated structure, drawn here as the row of numbers inside the node
- a query first finds the split node, where its two x-bounds part, and then follows one path down each side; every step hands over the subtree on the far side of the path, whose slab is entirely inside the query
- such a subtree is never entered: its node already lists every y below it in order, so the points to report are one contiguous run of that row
|
| Advantages: |
- a range query costs \(O(\log^2 n + t)\) in 2D to report \(t\) points — two paths of \(O(\log n)\) nodes, each claiming a subtree whose row costs another \(O(\log n)\) to search
- fractional cascading brings that down to \(O(\log n + t)\): the row search is done once at the split node, and each child's position is reached by a stored pointer
|
| Disadvantages: |
- \(O(n \log n)\) space in 2D, and \(O(n \log^{k-1} n)\) in \(k\) dimensions — every point is stored once per level of the main tree
- a range query costs \(O(\log^{k-1} n)\) in \(k\) dimensions, which is no longer practical for, say, \(k \ge 6\)
|