Prefix Sum arrays are one of the most commonly used data structures in competitive programming.
The basic question is this: Given an array A that won’t change, we want to answer Q queries of the form [l,r] asking for the sum of A[l] + A[l+1] … A[r].
Naively solving this problem by iterating from l to r will end with a time complexity of O(NQ), far too slow. Instead we can employ prefix sums to solve this problem in O(N+Q).
Define an array PSA[i] = A[1] + A[2] + A[3] + A[4] … A[i]
We can easily compute PSA[i] in O(N) by doing the following:
| for(int i = 1; i <= N; i++){ psa[i] = psa[i-1] + A[i]; } |
Now notice that if we want to query [L, R] it is simply equal to PSA[R] – PSA[L-1] where PSA[0] = 0.
This is because PSA[R] = A[1] + A[2] … A[R] and PSA[L-1] = A[1] + A[2] … A[L-1]. Then PSA[R] – PSA[L-1] = A[L]+A[L+1] … A[R]. Solved.
| for(int i = 1; i <= N; i++){ psa[i] = psa[i-1] + A[i]; } for(int i = 0; i < Q; i++){ int l, r; cin >> l >> r; cout << psa[r] – psa[l-1] << ‘\n’; } |
We can also do prefix sum arrays for other functions such as XOR, multiplication, etc. As long as the function has a way to invert (division and multiplication, subtraction and addition), it is possible to use a PSA.
Challenge: https://dmoj.ca/problem/bts18p6
(Hint: Use multiple prefix sum arrays, and also we can find the prefix sum array of the prefix sum array to simulate quadratic differences).