You could potentially do better than N^2 (ish) by approximating. Quantize the world into a grid, add up mass at each grid point. Then each particle is affected

You could potentially do better than N^2 (ish) by approximating. Quantize the world into a grid, add up mass at each grid point. Then each particle is affected by this weighted grid, which is made up of a relatively small number of pseudo-particles. Of course, you'd still need to fall back to N^2 for the nearest particles, or the accuracy would be unusably bad. But it's a much smaller N.