Prefix Sums: Answer Range Queries in Constant Time

Range sums by subtraction

For an array a, define prefix[i] as the sum of the first i elements. Use a leading zero: prefix[0] = 0, and prefix[i + 1] = prefix[i] + a[i]. Then the inclusive range from index left through right is prefix[right + 1] - prefix[left].

def build_prefix(nums):
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

Building takes O(n), each query takes O(1), and storage is O(n). The leading-zero convention avoids a special case when a range begins at index zero. For many queries over an unchanged array, this is usually preferable to summing each range repeatedly.

Count subarrays with a target sum

For a running prefix total current, a previous prefix current - target means the elements between those two prefix positions sum to the target. Keep a frequency map of prefix totals already seen. This works with negative values, unlike a basic sum sliding window.

from collections import defaultdict

def count_target_subarrays(nums, target):
    frequencies = defaultdict(int)
    frequencies[0] = 1
    total = count = 0
    for value in nums:
        total += value
        count += frequencies[total - target]
        frequencies[total] += 1
    return count

Each prefix is processed once: expected O(n) time with a hash map and O(n) worst-case space. Increment the frequency only after checking the current prefix, so an empty subarray is not counted as a nonempty match.

Two-dimensional prefix sums

For a grid, store the sum of the rectangle from the top-left corner through each cell. A rectangle query can then combine four corner totals using inclusion-exclusion: add the large top-left prefix, subtract the areas above and to the left, then add back their overlapping top-left area once. This takes O(rows × columns) preprocessing and O(1) per rectangle query.

Prefix sums are less suitable when the array changes often; changing one value affects every later prefix. For frequent updates and range queries, a Fenwick tree or segment tree may be a better fit.