Random crap I stumbled across while thinking about something else...
http://en.wikipedia.org/wiki/Convolution
Particularly using the Fourier transform is nice cause it makes it a simple product of the functions. (O(n) for a discrete function - just pointwise multiply)
iirc the FFT is O(n log n) which is not quite in Noah's O(log n) time but will get a solution. Or, because the function is a box, just use prior knowledge to determine the equivalent wavelet and directly compute the product one way. You could probably get O(log m) that way with a class that uses m identical attacks, since you are getting the same product multiple times (1+2 = 3+4 = 5+6, ... then 1+2+3+4, 5+6+7+8, etc.).
http://en.wikipedia.org/wiki/Convolution
Particularly using the Fourier transform is nice cause it makes it a simple product of the functions. (O(n) for a discrete function - just pointwise multiply)
iirc the FFT is O(n log n) which is not quite in Noah's O(log n) time but will get a solution. Or, because the function is a box, just use prior knowledge to determine the equivalent wavelet and directly compute the product one way. You could probably get O(log m) that way with a class that uses m identical attacks, since you are getting the same product multiple times (1+2 = 3+4 = 5+6, ... then 1+2+3+4, 5+6+7+8, etc.).