On 1/2/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > wont it take O(n^2) memory the partial sum of any "distance" would take O(n^2) memory, the partial sum from the first element to any element of the array takes O(n) memory.
If you want the sum from the i-th to the j-th element, just compute partial-sum-to-j-th less partial-sum-to-i-th element, am I wrong ? (maybe: I'm quite tired nowadays ...:) If you access both arrays in O(1) time (definition of array:) you can compute sum from i-th to j-th in O(1) time. bye ! Mattia Merzi.
