Using prefix sums to answer range sum queries in O(1) time after an O(n) preprocessing step.
The prefix sum technique is a powerful tool for efficiently handling range sum queries on a static array. A range sum query asks for the sum of elements in a given range, say from index `i` to `j`. The naive approach would be to iterate through the array from `i` to `j` and sum up the elements, which takes O(j - i + 1) or O(n) time in the worst case. If you have many such queries, this can become very slow. The prefix sum technique optimizes this by performing an O(n) preprocessing step. We create a new array, let's call it `prefix`, of the same size. `prefix[k]` will store the sum of all elements from the original array from index 0 up to `k`. This can be calculated in a single pass: `prefix[k] = prefix[k-1] + arr[k]`. Once this prefix sum array is built, any range sum query for `[i, j]` can be answered in O(1) time. The sum of elements from `i` to `j` is simply `prefix[j] - prefix[i-1]`. (A careful check is needed for the `i=0` case). This trade-off of a one-time preprocessing cost for lightning-fast query times is a common theme in algorithm design. The concept can also be extended to 2D arrays to calculate the sum of a rectangular submatrix in O(1) time after O(n*m) preprocessing.