Data Structures & Algorithms Cheatsheet

Prefix Sums and Difference Arrays

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

Prefix sums trade O(n) preprocessing for O(1) range queries. A difference array is the dual: O(1) range updates, O(n) to read back.

Structure	Build	Range query	Range update	Space
raw array	—	O(n)	O(1) point	O(1)
prefix sum	O(n)	O(1)	O(n) rebuild	O(n)
2D prefix sum	O(rc)	O(1)	O(rc) rebuild	O(rc)
difference array	O(n)	O(n) after finalize	O(1)	O(n)
Fenwick tree (BIT)	O(n)	O(log n)	O(log n) point	O(n)
segment tree	O(n)	O(log n)	O(log n)	O(n)

Rule of thumb: queries only means prefix sums. Updates plus queries means a Fenwick or segment tree. Updates then one final read means a difference array.

1D Prefix Sums

pre[i] is the sum of the first i elements, so pre[0] = 0. The extra leading zero removes every special case.

def build_prefix(a):
    pre = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        pre[i + 1] = pre[i] + x
    return pre

# sum of a[l..r] inclusive
def range_sum(pre, l, r):
    return pre[r + 1] - pre[l]

# itertools shortcut
from itertools import accumulate
pre = [0] + list(accumulate(a))

Variants that use the same skeleton:

Goal	Accumulate with	Query
range sum	`+`	`pre[r+1] - pre[l]`
range product	`*`	needs zero handling, prefer logs
range XOR	`^`	`pre[r+1] ^ pre[l]`
range min or max	not invertible	use a sparse table or segment tree
count of vowels in range	`+ (ch in "aeiou")`	same subtraction

Min and max are not invertible, so there is no prefix trick for them. That is exactly why sparse tables and segment trees exist.

Prefix Sums With A Hash Map

This is the pattern that handles negative numbers, where sliding windows fail. Store how many times each prefix value has been seen.

def subarray_sum_equals_k(nums, k):
    """Count subarrays summing to exactly k. Works with negatives. O(n)."""
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1                     # the empty prefix
    total = ans = 0
    for x in nums:
        total += x
        ans += seen[total - k]      # every earlier prefix that closes a match
        seen[total] += 1
    return ans

def longest_subarray_sum_k(nums, k):
    """Longest such subarray. Keep the FIRST index of each prefix."""
    first = {0: -1}
    total = best = 0
    for i, x in enumerate(nums):
        total += x
        if total - k in first:
            best = max(best, i - first[total - k])
        if total not in first:
            first[total] = i        # never overwrite, earlier is longer
    return best

def subarray_divisible_by_k(nums, k):
    """Count subarrays whose sum % k == 0. Bucket by remainder."""
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1
    total = ans = 0
    for x in nums:
        total = (total + x) % k     # Python % is always non-negative for k > 0
        ans += seen[total]
        seen[total] += 1
    return ans

def find_max_length_equal_01(nums):
    """Longest subarray with equal 0s and 1s: map 0 to -1, find sum 0."""
    first = {0: -1}
    total = best = 0
    for i, x in enumerate(nums):
        total += 1 if x == 1 else -1
        if total in first:
            best = max(best, i - first[total])
        else:
            first[total] = i
    return best

Counting versus longest is the fork: counting needs a frequency map and inserts every time, longest needs a first-seen map and never overwrites.

2D Prefix Sums

pre[r][c] is the sum of the rectangle from (0,0) to (r-1,c-1). Build with inclusion-exclusion, query the same way.

def build_2d(g):
    rows, cols = len(g), len(g[0])
    pre = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            pre[r + 1][c + 1] = (g[r][c]
                                 + pre[r][c + 1]
                                 + pre[r + 1][c]
                                 - pre[r][c])
    return pre

def rect_sum(pre, r1, c1, r2, c2):
    """Inclusive corners (r1, c1) to (r2, c2)."""
    return (pre[r2 + 1][c2 + 1]
            - pre[r1][c2 + 1]
            - pre[r2 + 1][c1]
            + pre[r1][c1])

The + pre[r1][c1] term is added back because the top-left block was subtracted twice. Forgetting it is the single most common bug in this template.

Difference Arrays

To add val to every index in [l, r], touch two cells. Prefix-sum the result once at the end.

def range_updates(n, updates):
    """updates: list of (l, r, val), all inclusive. O(n + u)."""
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l] += val
        diff[r + 1] -= val
    out, run = [], 0
    for i in range(n):
        run += diff[i]
        out.append(run)
    return out

def car_pooling(trips, capacity):
    """Each trip is (passengers, start, end). Sweep the timeline."""
    diff = [0] * 1001
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num            # passengers leave at end, exclusive
    run = 0
    for d in diff:
        run += d
        if run > capacity:
            return False
    return True

// Java: same two-touch update, note the n + 1 length
int[] diff = new int[n + 1];
for (int[] u : updates) { diff[u[0]] += u[2]; diff[u[1] + 1] -= u[2]; }
int[] out = new int[n];
for (int i = 0, run = 0; i < n; i++) { run += diff[i]; out[i] = run; }

The 2D version touches four corners:

diff[r1][c1] += v
diff[r1][c2 + 1] -= v
diff[r2 + 1][c1] -= v
diff[r2 + 1][c2 + 1] += v
# then prefix-sum across rows, then down columns

Fenwick Tree For Updates Plus Queries

When point updates and range queries interleave, a Fenwick tree (binary indexed tree) gives O(log n) for both in about fifteen lines.

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.t = [0] * (n + 1)      # 1-indexed internally

    def add(self, i, delta):        # i is 0-indexed
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i             # move to the parent

    def prefix(self, i):            # sum of a[0..i-1]
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):      # inclusive
        return self.prefix(r + 1) - self.prefix(l)

i & -i isolates the lowest set bit, which is the size of the block each node covers.

Gotchas

Off-by-one on the length. pre and diff are size n + 1. Writing diff[r + 1] when r == n - 1 needs that extra slot.
Inclusive or exclusive. Decide once, write it in a comment, and keep every query consistent. Mixing conventions is the top source of wrong answers here.
Sliding window versus prefix map. Windows require non-negative values. Any problem with negatives goes to the prefix hash map.
Seed seen[0] = 1 and first[0] = -1. Without them, subarrays that start at index 0 are missed.
Overflow. Prefix sums grow to n × max, so use long in Java and C++ even when the elements are int.
Modulo of negatives. Python -7 % 3 is 2, but Java and C++ give -1. Normalize with ((x % k) + k) % k outside Python.
Rebuilding after an update is O(n). If updates are frequent, a prefix array is the wrong structure, reach for Fenwick or a segment tree.