arrayscomplexitydsa
Prefix sums make range queries constant time
Anonymous
For an array a, build prefix with prefix[0] = 0 and prefix[i + 1] = prefix[i] + a[i]. Then the sum over half-open range [left, right) is prefix[right] - prefix[left], so each query takes O(1) after O(n) preprocessing. Check the integer range if values or ranges can be large.
0