For rigid bodies, given reasonably temporally coherent motion between time steps, you can get it down to O(n) with sweep and prune approaches [1]. These might not be the best choice for hair simulation, though.

[1] https://en.wikipedia.org/wiki/Sweep_and_prune