The issue isn't structure but rather density. If you have N values ranging from -M to M, the "obvious" solution is O(N^2) and the convolution us O(M log M). S

The issue isn't structure but rather density. If you have N values ranging from -M to M, the "obvious" solution is O(N^2) and the convolution us O(M log M). So if you have lots of values within a narrow range the convolution wins.