Prefix Sums & Difference Arrays

This builds on Two Pointers & Sliding Windows. There, the sliding window optimized over contiguous subarrays, but only when feasibility was monotone in width — a sum that grows as the window widens, which needs every entry to be positive. The moment negative numbers enter, that monotonicity is gone: widening a window can lower its sum, so shrinking from the left no longer safely tightens it. This lesson supplies a technique that works with negative entries. Prefix sums restate a subarray's sum as the difference of two precomputed running totals, and that reframing answers range-sum queries in $O (1)$ and counts exact-sum subarrays in $O (n)$ regardless of sign.

Prefix sums

The sliding window assumed we could update a sum incrementally. Prefix sums generalize this to answer any range-sum query in $O (1)$ after a linear precompute. Define

P [0] = 0, P [i] = a [0] + a [1] + \dots + a [i - 1] = j < i \sum a [j],

so $P$ has length $n + 1$ and is built in one pass: $P [i] = P [i - 1] + a [i - 1]$ . Then the sum of any subarray telescopes:

sum (l, r) = a [l] + \dots + a [r] = P [r + 1] - P [l] .

The conventions here are chosen to kill off-by-one bugs, which are this technique's only real hazard. $P$ has length $n + 1$ , one entry per boundary between elements rather than per element; $P [i]$ is the sum of the first $i$ elements, exclusive of $a [i]$ . The sentinel $P [0] = 0$ makes $sum (0, r) = P [r + 1] - P [0]$ work with no special case for ranges that touch the left edge, and an empty range returns $0$ for free. When a range-sum looks off by one element, the fix is almost always at the boundary: check whether your convention is inclusive or exclusive at each end before touching anything else.

With

P [i] = \sum_{j < i} a [j]

, any range sum is the difference of two prefix entries:

sum (l, r) = P [r + 1] - P [l]

The highlighted entries are $P [2] = 4$ and $P [5] = 14$ ; their difference $10$ is exactly $a [2] + a [3] + a [4] = 4 + 1 + 5$ . One subtraction, no rescanning.

To fix the whole construction in one trace, build $P$ for $a = ⟨ 3, 1, 4, 1, 5, 9 ⟩$ from left to right, then answer two queries:

Build: $P [0] = 0$ ; $P [1] = 0 + 3 = 3$ ; $P [2] = 3 + 1 = 4$ ; $P [3] = 4 + 4 = 8$ ; $P [4] = 8 + 1 = 9$ ; $P [5] = 9 + 5 = 14$ ; $P [6] = 14 + 9 = 23$ . One addition per boundary, $O (n)$ total.
Query $sum (2, 4)$ : $P [5] - P [2] = 14 - 4 = 10$ , matching $4 + 1 + 5$ .
Query $sum (0, 5)$ (the whole array): $P [6] - P [0] = 23 - 0 = 23$ , matching $3 + 1 + 4 + 1 + 5 + 9$ . Because $P [0] = 0$ , the left-edge case needs no branch.

prefix_sums.pypython

from typing import Sequence

class PrefixSum:
  """
    A precomputed prefix-sum table over a fixed array of integers,\n
    supporting O(1) inclusive range-sum queries.\n
  """

  def __init__(self, values: Sequence[int]) -> None:
    """
      Build the prefix table `prefix[0 .. n]` from `values` in one pass.\n
    """
    # each entry carries the running total of everything before it.
    self.prefix: list[int] = [0 for _ in range(len(values) + 1)]
    for index, value in enumerate(values):
      self.prefix[index + 1] = self.prefix[index] + value

  def range_sum(self, left: int, right: int) -> int:
    """
      The sum of `values[left .. right]` inclusive, in O(1). Requires\n
      `0 <= left <= right < n`.\n
    """
    return self.prefix[right + 1] - self.prefix[left]

Counting subarrays with sum $= k$ . Prefix sums turn a $Θ (n^{2})$ subarray scan into $O (n)$ for Subarray Sum Equals K. A subarray $(i, j)$ has sum $k$ iff $P [j + 1] - P [i] = k$ , i.e. $P [i] = P [j + 1] - k$ . So as we sweep a running prefix $P [j + 1]$ left to right, the number of valid left endpoints is the number of earlier prefixes equal to $P [j + 1] - k$ . Keep a hash map of prefix-value frequencies seen so far:

Algorithm:

\textsc{CountSubarrays}(a, k)

— number of subarrays summing to

k

, in

O(n)

1
$\text{count} \gets 0,\ \ \text{prefix} \gets 0$
2
$\text{freq} \gets \{\,0 : 1\,\}$
empty prefix seen once
3
for $j \gets 0$ to $n-1$ do
4
$\text{prefix} \gets \text{prefix} + a[j]$
5
$\text{count} \gets \text{count} + \text{freq}[\text{prefix} - k]$
0 if absent
6
$\text{freq}[\text{prefix}] \gets \text{freq}[\text{prefix}] + 1$
7
return $\text{count}$

Seeding freq with ${0 : 1}$ accounts for subarrays that start at index $0$ (those need $P [i] = 0$ ). One pass, $O (n)$ time and space. Watch it on $a = ⟨ 1, 2, 3 ⟩$ with $k = 3$ :

$j = 0$ : prefix $1$ ; look up $1 - 3 = - 2$ , absent, count stays $0$ ; record $freq [1] = 1$ .
$j = 1$ : prefix $3$ ; look up $0$ , which the seed holds once — count $1$ (the subarray $⟨ 1, 2 ⟩$ ); record $freq [3] = 1$ .
$j = 2$ : prefix $6$ ; look up $3$ , present once — count $2$ (the subarray $⟨ 3 ⟩$ ); done.

The map after the sweep is ${0 : 1, 1 : 1, 3 : 1, 6 : 1}$ , and the two hits found the two subarrays $⟨ 1, 2 ⟩$ and $⟨ 3 ⟩$ , both summing to $3$ .

CountSubarrays

⟨ 1, 2, 3 ⟩

k = 3

. Each column is a step: the running prefix, the value

prefix - k

looked up, and the map entry that scores a hit. Two prior prefixes match, so two subarrays sum to

k

Two pitfalls hide in the bookkeeping. Dropping the ${0 : 1}$ seed silently loses every subarray that starts at index $0$ . And the lookup must happen before the insert: inserting first lets the current prefix match itself, which counts the empty subarray whenever $k = 0$ . The map stores counts, not mere presence, because distinct left endpoints can share a prefix value (any zero-sum stretch creates repeats), and each one is a separate subarray.

This works for any integers, positive or negative, unlike the sliding window, which needed positivity for monotonicity. A concrete case where the window fails but prefixes do not: on $a = ⟨ 3, - 1, - 2, 4 ⟩$ with $k = 0$ , the subarray $⟨ 3, - 1, - 2 ⟩$ sums to zero, yet no positive-only window argument can find it. The prefix sweep sees $P = ⟨ 0, 3, 2, 0, 4 ⟩$ and, at $j = 2$ where the running prefix returns to $0$ , looks up $0 - 0 = 0$ in the map, which the seed already holds once — scoring the hit. Restating the subarray condition as a relation between two prefix values, then sweeping once while remembering the prefixes already seen, is the standard fallback when negative entries break a window argument.

subarray_sum_equals_k.pypython

from collections import defaultdict
from typing import Sequence

def count_subarrays_with_sum(values: Sequence[int], target: int) -> int:
  """
    The number of contiguous subarrays of `values` whose sum equals\n
    `target`.\n
  """
  count: int = 0
  running_prefix: int = 0

  # the empty prefix has value 0 and has been seen once.
  prefix_frequency: dict[int, int] = defaultdict(int)
  prefix_frequency[0] = 1

  for value in values:
    # each earlier prefix equal to (running - target) closes a valid subarray.
    running_prefix += value
    count += prefix_frequency[running_prefix - target]
    prefix_frequency[running_prefix] += 1

  return count

Difference arrays, the dual

To apply many range updates "add $v$ to every $a [i \dots j]$ " and only then read the array, invert the relationship. Keep a difference array $D$ and for each update do $D [i] + = v$ and $D [j + 1] - = v$ , two $O (1)$ touches. A single prefix-sum pass over $D$ at the end materializes the final array, since $a [i] = D [0] + \dots + D [i]$ . Thus $m$ range-adds cost $O (m + n)$ instead of $O (mn)$ . Give $D$ length $n + 1$ so the $D [j + 1]$ poke stays in bounds when a range runs to the last element; the extra entry is never read back. The scheme's one limitation is batching: a query between updates forces a full sweep, and interleaved updates and queries call for a Fenwick tree instead.

Difference array on an initially zero

a

: the range-add

+ 5

a [1 .. 3]

pokes

D [1] + = 5

and

D [4] - = 5

, two

O (1)

touches; one prefix-sum sweep of

D

then materializes the update in

a

The mechanism is worth tracing on two overlapping updates. Start with $a = ⟨ 0, 0, 0, 0, 0 ⟩$ and $D = ⟨ 0, 0, 0, 0, 0, 0 ⟩$ . Apply "add $5$ to $a [1 \dots 3]$ ": $D [1] + = 5$ , $D [4] - = 5$ , giving $D = ⟨ 0, 5, 0, 0, - 5, 0 ⟩$ . Apply "add $2$ to $a [2 \dots 4]$ ": $D [2] + = 2$ , $D [5] - = 2$ , giving $D = ⟨ 0, 5, 2, 0, - 5, - 2 ⟩$ . Now one prefix-sum sweep of $D$ produces $a = ⟨ 0, 5, 7, 7, 2, 0 ⟩$ — position $2$ and $3$ received both updates ( $5 + 2 = 7$ ), position $4$ received only the second, and the two $O (1)$ pokes per update never touched the interior cells at all. Two range-adds, four pokes, one sweep, versus the six writes a direct loop would make.

difference_array.pypython

from __future__ import annotations

from typing import Sequence

class DifferenceArray:
  """
    Accumulates range-add updates over a fixed-length array, deferring the\n
    O(n) materialization until every update has been recorded.\n
  """

  def __init__(self, length: int) -> None:
    """
      Start over a zero array of `length` cells. An extra trailing slot\n
      absorbs the closing decrement of an update reaching the last index.\n
    """
    self.length: int = length
    self.diff: list[int] = [0 for _ in range(length + 1)]

  @classmethod
  def from_values(cls, values: Sequence[int]) -> DifferenceArray:
    """
      Seed a difference array whose materialization equals `values`.\n
    """
    # store each consecutive difference so the prefix sweep rebuilds values.
    instance = cls(len(values))
    previous: int = 0
    for index, value in enumerate(values):
      instance.diff[index] = value - previous
      previous = value

    return instance

  def range_add(self, left: int, right: int, value: int) -> None:
    """
      Schedule adding `value` to every cell in `array[left .. right]`\n
      inclusive, in O(1).\n
    """
    self.diff[left] += value
    self.diff[right + 1] -= value

  def materialize(self) -> list[int]:
    """
      The final array after all updates, via one prefix-sum sweep in O(n).\n
    """
    # a running prefix sum of the differences yields each final cell.
    result: list[int] = [0 for _ in range(self.length)]
    running: int = 0
    for index in range(self.length):
      running += self.diff[index]
      result[index] = running

    return result

Two dimensions

Prefix sums extend to two dimensions as well: precompute $P [i] [j] = \sum_{i^{'} < i, j^{'} < j} a [i^{'}] [j^{'}]$ , so $P_{X}$ for a grid point $X$ is the sum of the whole block between the origin (top-left) and $X$ . Any axis-aligned rectangle sum is then recovered by inclusion–exclusion with four lookups: with corners $A, B, C, D$ as in the figure, $P_{D}$ covers the query plus a strip above it and a strip to its left; subtracting $P_{B}$ removes the strip above, subtracting $P_{C}$ removes the strip to the left, and both subtractions remove the corner block twice, so $P_{A}$ is added back once. The table itself is built in one pass by the same identity read in reverse: $P [i] [j] = a [i - 1] [j - 1] + P [i - 1] [j] + P [i] [j - 1] - P [i - 1] [j - 1]$ .

2-D prefix sums, origin at top-left:

P_{X}

sums the block from the origin to

X

. Then

sum = P_{D} - P_{B} - P_{C} + P_{A}

: subtracting the two shaded strips removes the darker corner block twice, so add

P_{A}

back once

prefix_sum_2d.pypython

from typing import Sequence

class PrefixSum2D:
  """
    A precomputed 2-D prefix-sum table over a fixed integer grid, supporting\n
    O(1) inclusive rectangle-sum queries.\n
  """

  def __init__(self, grid: Sequence[Sequence[int]]) -> None:
    """
      Build the `(rows + 1) x (cols + 1)` prefix table from `grid`.\n
    """
    self.rows: int = len(grid)
    self.cols: int = len(grid[0]) if self.rows > 0 else 0
    self.prefix: list[list[int]] = [
      [0 for _ in range(self.cols + 1)] for _ in range(self.rows + 1)
    ]
    # each cell adds the strips above and left, minus their shared corner.
    for row in range(self.rows):
      for col in range(self.cols):
        self.prefix[row + 1][col + 1] = (
          grid[row][col]
          + self.prefix[row][col + 1]
          + self.prefix[row + 1][col]
          - self.prefix[row][col]
        )

  def rectangle_sum(
    self, top: int, left: int, bottom: int, right: int
  ) -> int:
    """
      The sum over the inclusive rectangle from `(top, left)` to\n
      `(bottom, right)`, in O(1).\n
    """
    return (
      self.prefix[bottom + 1][right + 1]
      - self.prefix[top][right + 1]
      - self.prefix[bottom + 1][left]
      + self.prefix[top][left]
    )

Beyond the sum: other prefix aggregates

The subtraction trick $P [r + 1] - P [l]$ works because addition has an inverse: to remove the contribution of a prefix, subtract it. Any aggregate whose combine operation is a group — has an identity and inverses — supports the same $O (1)$ range query. Two show up constantly.

Prefix XOR. Bitwise xor is its own inverse ( $x \oplus x = 0$ ), so with $X [i] = a [0] \oplus \dots \oplus a [i - 1]$ the xor of any range is $X [r + 1] \oplus X [l]$ . Counting subarrays with xor equal to $k$ is then the exact analogue of the sum count: sweep the running prefix-xor, and at each step look up how many earlier prefixes equal $prefix \oplus k$ (since $X [j + 1] \oplus X [i] = k \leftrightarrow X [i] = X [j + 1] \oplus k$ ). Same hash map, same $O (n)$ .

Prefix products. With no zeros, a prefix product supports range products by division, but the useful trick sidesteps division entirely: the product of all elements except self is $(prefix product before i) \times (suffix product after i)$ , two passes and no division, robust to zeros.

What does not carry over is min and max: they have no inverse, so a prefix-max array cannot answer an arbitrary range's maximum by two lookups. Range min/max over a static array needs a different structure — a sparse table for $O (1)$ queries, or the monotonic deque of the previous lesson for a sliding window. The dividing line comes down to invertibility: sum, xor, and count are invertible and yield $O (1)$ range queries off a prefix array; min and max are not.

From summed-area tables to Fenwick trees

The four-corner inclusion–exclusion that reads a rectangle sum off a 2-D prefix table is the discrete cousin of the summed-area table introduced to computer graphics by Crow (Summed-Area Tables for Texture Mapping, SIGGRAPH 1984): a preprocessed image where any axis-aligned box's average brightness is four lookups, used for fast texture filtering. The same table, under the name integral image, is what makes the Viola–Jones face detector (Viola & Jones, Rapid Object Detection Using a Boosted Cascade of Simple Features, CVPR 2001) evaluate its rectangular Haar features in constant time per feature — the technique behind the first practical real-time face detector, and still the textbook example of trading $O (n)$ preprocessing for $O (1)$ queries.

Prefix sums are also the point where this static idea meets its dynamic successor. The moment updates interleave with queries, a plain prefix array must be rebuilt on every write, $O (n)$ each; the Fenwick (binary indexed) tree of Fenwick (A New Data Structure for Cumulative Frequency Tables, Software: Practice and Experience, 1994) keeps prefix sums under point updates in $O (log n)$ per operation, and the segment tree generalizes further to range updates and non-sum aggregates. The difference-array trick in this lesson is the special case that makes Fenwick trees support range updates: a Fenwick tree over the difference array is the standard range-update, point-query structure.

Finally, the prefix-map trick for counting subarrays with a given sum is one instance of a broad pattern: canonicalize a subarray's answer as a function of two prefix states, then hash the prefix states. The same move counts subarrays with sum divisible by $k$ (hash the running prefix modulo $k$ ), subarrays with equal counts of two symbols (hash a running difference), and the longest such subarray (store the first index each prefix value appeared). Recognizing that a constraint on a range is really a relation between its two endpoints is the reusable idea underneath all of them.

Takeaways

Prefix sums $P [i] = \sum_{j < i} a [j]$ answer any range sum as $P [r + 1] - P [l]$ in $O (1)$ after an $O (n)$ precompute; the $P [0] = 0$ sentinel and boundary-not-element convention are what keep the off-by-one bugs away.
A hash map of prefix frequencies counts subarrays with sum $k$ in $O (n)$ , and — unlike the sliding window — works with negative entries, because it restates the constraint as a relation between two prefix values.
The difference-array dual applies $m$ range-adds in $O (m + n)$ : two $O (1)$ pokes per update, one prefix-sweep to materialize.
Prefix sums generalize to 2-D rectangle queries in $O (1)$ by four-corner inclusion–exclusion, the summed-area / integral-image trick.
Once updates and queries interleave, a static prefix array no longer suffices; upgrade to a Fenwick or segment tree.