Arrays & Prefix Sum — DSA Mastery

Array Operations

Click an operation to see it animated on the array.

Choose an operation above to see how it works.

Prefix Sum Visualizer

Select a range [L, R] to compute sum in O(1) using prefix array.

Original Array:

Prefix Sum Array:

L: R:

Set L and R, then click Compute Sum.

Why Arrays?

Memory Layout

Arrays store elements in contiguous memory. Address of arr[i] = base_address + i × element_size. This is why index access is O(1) — direct math, no traversal.

Operation	Time	Why
`arr[i]`	O(1)	Direct address calculation
`arr.append(x)`	O(1)*	Amortized (occasionally resizes)
`arr.pop()`	O(1)	Remove last, no shifting
`arr.insert(i, x)`	O(n)	Must shift all elements right
`arr.pop(i)`	O(n)	Must shift all elements left
`x in arr`	O(n)	Linear scan
`arr.sort()`	O(n log n)	TimSort in-place

Prefix Sum — The Key Trick

The Problem It Solves

If you need sum(arr[l..r]) a thousand times, computing it from scratch each time is O(n) per query = too slow. Prefix sum precomputes once, answers in O(1).

Analogy

Think of distances on a highway. prefix[i] = total distance from city 0 to city i. Distance from city l to city r = prefix[r+1] − prefix[l].

Off-by-one Watch!

prefix has length n+1 (prefix[0]=0 is sentinel). range_sum(l,r) = prefix[r+1] - prefix[l]. Don't forget the +1.

Difference Array

Use Case

Range update: add value to all elements from l to r — do this many times, then read. Naive: O(n) per update. Difference array: O(1) update, O(n) final pass.

# Difference array for range updates
def range_update(arr, updates):
    n = len(arr)
    diff = [0] * (n + 1)

    for l, r, val in updates:
        diff[l]     += val  # add starts here
        diff[r + 1] -= val  # subtract ends here

    # Apply prefix sum to get final array
    running = 0
    for i in range(n):
        running += diff[i]
        arr[i] += running
    return arr

Prefix Sum Template

def build_prefix(arr):
    # prefix[i] = sum of arr[0..i-1]
    # prefix[0] = 0 (empty sum — sentinel)
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i+1] = prefix[i] + x
    return prefix

def range_sum(prefix, l, r):
    # Sum of arr[l..r] inclusive
    return prefix[r+1] - prefix[l]

# Example:
arr =    [3, 1, 4, 1, 5, 9, 2]
# pfx = [0, 3, 4, 8, 9,14,23,25]
# sum(arr[2..5]) = pfx[6]-pfx[2] = 23-4 = 19 ✓

Common Array Patterns

# Kadane's algorithm — Max subarray sum
def max_subarray(nums):
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)  # extend or restart
        best = max(best, cur)
    return best

# 2D prefix sum
def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    pre = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            pre[r][c] = (grid[r-1][c-1]
                + pre[r-1][c] + pre[r][c-1]
                - pre[r-1][c-1])
    return pre

LeetCode Problems

EasyRunning Sum of 1D ArrayPrefix Sum basics
EasyFind Pivot IndexPrefix = Suffix check
MediumSubarray Sum Equals KPrefix sum + HashMap
MediumProduct of Array Except SelfLeft & right prefix product
MediumMaximum SubarrayKadane's algorithm
MediumRange Sum Query 2D2D prefix sum
HardCount of Range SumPrefix + merge sort