Prefix Sum

Define prefix[i] as the sum of the first i elements. That means prefix[0] = 0, prefix[1] = nums[0], and prefix[n] is the total sum of the whole array. The extra leading zero represents the empty prefix and makes boundary math clean.

With this definition, the sum of nums[l..r] is prefix[r + 1] - prefix[l]. The right boundary includes elements through r, and the left boundary removes everything before l.

Without prefix sums, each range query may scan the requested range, costing O(length) or O(n) in the worst case. If there are many queries, that repeated scanning dominates the runtime.

Building the prefix array costs O(n) once. After that, every range sum is O(1). The trade-off is O(n) extra space, which is usually worth it when the number of queries is large or when subarray sums are checked repeatedly.

Look for words like range sum, subarray sum, balance, cumulative, number of queries, or sum between indices. Prefix sums also appear when the problem asks for equal numbers of two categories: convert one category to +1, the other to -1, and equal balance becomes repeated prefix value.

For subarray sum equals k, the range formula becomes currentPrefix - earlierPrefix = k. Rearranged, you need to know how many earlier prefixes equal currentPrefix - k, which is why prefix sums often pair with a HashMap.

For matrices, a two-dimensional prefix sum stores the total rectangle from the top-left corner through each cell. A query rectangle can then be answered by adding the large rectangle, subtracting the areas above and left, and adding back the overlapped corner.

The same principle applies: precompute cumulative structure once, then answer many rectangle queries quickly. The main risk is off-by-one indexing, so many implementations allocate one extra row and one extra column for empty boundaries.