2D structure
Primary BST sorts by x. Each node stores secondary BST of its subtree sorted by y.
Advertisement
Query 2D range
Find x-range in primary tree via descent. At each covered node, range-query y in secondary tree. Combine.
Advertisement
Space
O(N log N) for 2D. O(N log^(d-1) N) generally. Prohibitive at high d.
Fractional cascading
Reduces 2D query from O(log² N) to O(log N) by preprocessing. Advanced but standard technique.