Hacker News Reader

What are useful applications for this algorithm? The Wikipedia article lists a few, but they seem rather specialized.

https://courses.csail.mit.edu/6.851/ covers them. If I recall, one use was speeding up search in range trees.

Article says:

> 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".

https://archive.is/UysEd

I will never know if I could have actually invented it or not.

The website doesn't load and I don't know what we're talking about.