> Fractional cascading is a very useful transformation, used in a variety of contexts including layered range trees and 3D orthogonal range searching. In fact, (...)
> Here's another obvious thing we can do: for every element in the first array, let's give it a pointer to the element with the same value in the second array
I don't understand why they made this leap after describing an O(k log n) algorithm. This seems comparatively a very expensive to do.
I guess an unspoken assumption is that the data changes rarely or never, so a preprocessing step can be amortized over a lot of searches, making it essentially "free".
