The problem
Search value V in each of K sorted lists. Naive: K × O(log N).
Advertisement
The augmentation
Add pointers from each element to the corresponding position in next list. After first binary search, follow pointers.
Advertisement
Trick: sampling
Insert every 2nd element from next list into current. Preserves cost bounds. Bridge for search.
Applications
Range trees (2D queries in O(log N) instead of O(log² N)). Persistent search trees. Geometric problems.