--- title: Prefix Sums & Difference Arrays module: Sequences & Strings moduleNumber: 5 lessonNumber: 2 order: 502 summary: | Prefix sums precompute the running total once so that any range-sum query is a single subtraction, $P[r{+}1]-P[l]$, in $O(1)$. A hash map of prefix frequencies then counts subarrays summing to $k$ in $O(n)$ — even with negative entries, where the sliding window fails. The difference-array dual turns $m$ range-adds into $O(m+n)$, and the whole idea lifts to 2-D rectangle sums by inclusion–exclusion. topics: [Array Techniques] sources: - book: CLRS ref: "Ch. 2 — Getting Started" - book: Skiena ref: "§ — Sorting & array techniques" - book: Erickson ref: "Ch. — Arrays and Amortization" practice: - title: 'Subarray Sum Equals K' slug: subarray-sum-equals-k difficulty: Medium - title: 'Range Sum Query - Immutable' slug: range-sum-query-immutable difficulty: Easy - title: 'Range Sum Query 2D - Immutable' slug: range-sum-query-2d-immutable difficulty: Medium - title: 'Continuous Subarray Sum' slug: continuous-subarray-sum difficulty: Medium --- This builds on [Two Pointers & Sliding Windows](/algorithms/sequences/two-pointers-and-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**](/algorithms/data-structures/fenwick-and-segment-trees) generalize this to answer _any_ range-sum query in $O(1)$ after a linear precompute. Define $$ P[0] = 0, \qquad P[i] = a[0] + a[1] + \cdots + a[i-1] = \sum_{j=stealth] \definecolor{acc}{HTML}{2348F2} % array a (6 cells), indices 0..5, sitting above gaps of P \node[font=\small] at (-1.1,0) {$a$}; \node[cell] (a0) at (0.4,0) {$3$}; \node[cell] (a1) at (1.2,0) {$1$}; \node[cell] (a2) at (2.0,0) {$4$}; \node[cell] (a3) at (2.8,0) {$1$}; \node[cell] (a4) at (3.6,0) {$5$}; \node[cell] (a5) at (4.4,0) {$9$}; % prefix P (7 boundaries) below, aligned to cell edges \node[font=\small] at (-1.1,-1.6) {$P$}; \node[pcell] (p0) at (0.0,-1.6) {$0$}; \node[pcell] (p1) at (0.8,-1.6) {$3$}; \node[pcell, acc, very thick] (p2) at (1.6,-1.6) {$4$}; \node[pcell] (p3) at (2.4,-1.6) {$8$}; \node[pcell] (p4) at (3.2,-1.6) {$9$}; \node[pcell, acc, very thick] (p5) at (4.0,-1.6) {$14$}; \node[pcell] (p6) at (4.8,-1.6) {$23$}; % brace over a[2..4] showing the queried range \draw[acc, thick] (1.6,0.6) -- (1.6,0.8) -- (4.0,0.8) -- (4.0,0.6); \node[acc, font=\small] at (2.8,1.15) {sum(2, 4) = P[5] - P[2] = 10}; \end{tikzpicture} $$ 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 = \langle 3,1,4,1,5,9\rangle$ 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 $\text{sum}(2,4)$: $P[5]-P[2]=14-4=10$, matching $4+1+5$. - Query $\text{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. ::impl{algo="prefix_sums"} **Counting subarrays with sum $= k$.** Prefix sums turn a $\Theta(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 caption: $\textsc{CountSubarrays}(a, k)$ — number of subarrays summing to $k$, in $O(n)$ $\text{count} \gets 0,\ \ \text{prefix} \gets 0$ $\text{freq} \gets \{\,0 : 1\,\}$ // empty prefix seen once for $j \gets 0$ to $n-1$ do $\text{prefix} \gets \text{prefix} + a[j]$ $\text{count} \gets \text{count} + \text{freq}[\text{prefix} - k]$ // 0 if absent $\text{freq}[\text{prefix}] \gets \text{freq}[\text{prefix}] + 1$ 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 = \langle 1, 2, 3\rangle$ with $k = 3$: - $j = 0$: prefix $1$; look up $1 - 3 = -2$, absent, count stays $0$; record $\text{freq}[1] = 1$. - $j = 1$: prefix $3$; look up $0$, which the seed holds once — count $1$ (the subarray $\langle 1,2\rangle$); record $\text{freq}[3] = 1$. - $j = 2$: prefix $6$; look up $3$, present once — count $2$ (the subarray $\langle 3\rangle$); done. The map after the sweep is $\{0{:}1,\,1{:}1,\,3{:}1,\,6{:}1\}$, and the two hits found the two subarrays $\langle 1,2\rangle$ and $\langle 3\rangle$, both summing to $3$. $$ % caption: $\textsc{CountSubarrays}$ on $\langle 1,2,3\rangle$, $k{=}3$. Each column is a % step: the running prefix, the value $\text{prefix}-k$ looked up, and the map % entry that scores a hit. Two prior prefixes match, so two subarrays sum to $k$ \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.3,0) {$a[j]$:}; \node[anchor=east] at (-0.3,-0.65) {running $P$:}; \node[anchor=east] at (-0.3,-1.3) {seek P less k:}; \node[anchor=east] at (-0.3,-1.95) {hits:}; \foreach \j/\a/\p/\lu/\h in {0/1/1/{-2}/0, 1/2/3/{0}/1, 2/3/6/{3}/1} { \node[draw=black, minimum size=7mm, inner sep=1pt] at (\j*2.0,0) {$\a$}; \node at (\j*2.0,-0.65) {$\p$}; \node at (\j*2.0,-1.3) {\lu}; } \node[acc] at (0*2.0,-1.95) {0}; \node[acc] at (1*2.0,-1.95) {1}; \node[acc] at (2*2.0,-1.95) {1}; \node[acc, anchor=west] at (4*2.0-0.6,-1.95) {total 2}; \end{tikzpicture} $$ 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 = \langle 3, -1, -2, 4\rangle$ with $k = 0$, the subarray $\langle 3,-1,-2\rangle$ sums to zero, yet no positive-only window argument can find it. The prefix sweep sees $P = \langle 0,3,2,0,4\rangle$ 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. ::impl{algo="subarray_sum_equals_k"} ## Difference arrays, the dual To apply many _range updates_ "add $v$ to every $a[i \ldots j]$" and only then read the array, invert the relationship. Keep a difference array $D$ and for each update do $D[i] \mathrel{+}= v$ and $D[j+1] \mathrel{-}= v$, two $O(1)$ touches. A single prefix-sum pass over $D$ at the end materializes the final array, since $a[i] = D[0] + \cdots + 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](/algorithms/data-structures/fenwick-and-segment-trees) instead. $$ % caption: Difference array on an initially zero $a$: the range-add $+5$ to % $a[1\mathinner{\ldotp\ldotp} 3]$ pokes $D[1]\mathrel{+}{=}5$ and % $D[4]\mathrel{-}{=}5$, two $O(1)$ touches; one prefix-sum sweep of $D$ then % materializes the update in $a$ \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \node[font=\footnotesize] at (-1.2,0) {$D$}; \foreach \i/\v in {0/0,2/0,3/0,5/0} { \node[draw, minimum size=8mm, inner sep=1pt] (d\i) at (\i*0.95,0) {$\v$}; \node[font=\footnotesize] at (\i*0.95,0.62) {\i}; } \node[draw=acc, very thick, minimum size=8mm, inner sep=1pt] (d1) at (0.95,0) {+5}; \node[font=\footnotesize] at (0.95,0.62) {1}; \node[draw=acc, very thick, minimum size=8mm, inner sep=1pt] (d4) at (3.8,0) {-5}; \node[font=\footnotesize] at (3.8,0.62) {4}; \node[font=\footnotesize] at (-1.2,-1.5) {$a$}; \foreach \i/\v in {0/0,1/5,2/5,3/5,4/0,5/0} { \node[draw, minimum size=8mm, inner sep=1pt, fill=acc!8] (s\i) at (\i*0.95,-1.5) {$\v$}; } \node[font=\footnotesize, acc] at (2.4,-2.2) {one sweep $\Rightarrow$ +5 exactly on a[1..3]}; \end{tikzpicture} $$ The mechanism is worth tracing on two overlapping updates. Start with $a = \langle 0,0,0,0,0\rangle$ and $D = \langle 0,0,0,0,0,0\rangle$. Apply "add $5$ to $a[1\ldots 3]$": $D[1] \mathrel{+}= 5$, $D[4] \mathrel{-}= 5$, giving $D = \langle 0,5,0,0,-5,0\rangle$. Apply "add $2$ to $a[2\ldots 4]$": $D[2] \mathrel{+}= 2$, $D[5] \mathrel{-}= 2$, giving $D = \langle 0,5,2,0,-5,-2\rangle$. Now one prefix-sum sweep of $D$ produces $a = \langle 0,5,7,7,2,0\rangle$ — 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. ::impl{algo="difference_array"} ## Two dimensions Prefix sums extend to **two dimensions** as well: precompute $P[i][j] = \sum_{i'=stealth, font=\small] \definecolor{acc}{HTML}{2348F2} \useasboundingbox (-1.3,-1.1) rectangle (5.6,4.6); % strips subtracted from P_D; their overlap is the doubly removed corner \fill[black] (0,2.8) rectangle (3.6,4); \fill[black] (0,0.8) rectangle (1.4,2.8); \fill[black] (0,2.8) rectangle (1.4,4); \draw[black] (0,0) rectangle (4,4); % query rectangle \fill[acc!15] (1.4,0.8) rectangle (3.6,2.8); \draw[acc, very thick] (1.4,0.8) rectangle (3.6,2.8); % origin marker \fill[black] (0,4) circle (1.6pt); \node[font=\footnotesize, black] at (-0.7,4.25) {origin}; % corner dots labelled A,B,C,D measured from the origin \foreach \x/\y in {1.4/2.8, 3.6/2.8, 1.4/0.8, 3.6/0.8} { \fill[acc] (\x,\y) circle (1.6pt); } \node[font=\footnotesize] at (1.15,3.05) {$A$}; \node[font=\footnotesize] at (3.85,3.05) {$B$}; \node[font=\footnotesize] at (1.15,0.55) {$C$}; \node[font=\footnotesize] at (3.85,0.55) {$D$}; \node[acc, font=\footnotesize] at (2.5,1.8) {query}; \node[font=\footnotesize, black] at (2.5,3.4) {$P_B$ strip}; \node[font=\footnotesize, black, rotate=90] at (0.7,1.8) {$P_C$ strip}; \node[font=\footnotesize, align=center] at (2.0,-0.6) {sum = $P_D$ - $P_B$ - $P_C$ + $P_A$}; \end{tikzpicture} $$ ::impl{algo="prefix_sum_2d"} ## 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 \cdots \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 $\text{prefix} \oplus k$ (since $X[j+1] \oplus X[i] = k \iff 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 $(\text{prefix product before } i) \times (\text{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](/algorithms/sequences/two-pointers-and-windows) 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](/algorithms/data-structures/fenwick-and-segment-trees) 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