The ML problem involved, for a set of points on a line, computing the sum (over all the pairs of distinct points) of a function d(x_i,x_j) that is, in some sense, well behaved. The purpose was to compute the similarity of two sets of real numbers.

It turns out this can be done (to sufficient accuracy) in nearly linear time using something called the fast multipole method.

http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/F...

I wouldn't consider the "O(log n) chunks" trick all that complex, btw, although Tarjan did have to point it out to me when I should have used it.