Prefix Sum

    DSA · Beginner

    Definition

    A prefix sum array stores the running total so any range sum is computed in O(1).

    Turns repeated range-sum queries from O(n) each into O(1) each.

    Diagram

    a: 2 4 1 3pre: 0 2 6 7 10sum(1..2) = 7 − 2 =…

    Flowchart

    Create pre[0] = 0pre[i+1] = pre[i] + a[i]Sum(l..r) = pre[r+1] − pre[l]Answer each query in O(1)

    Example: Range sum query

    a = [2, 4, 1, 3]
pre = [0]
for x in a:
    pre.append(pre[-1] + x)
print(pre[3] - pre[1])

    Output: 5

    Complexity

    Build O(n) · Query O(1)

    Key points

    • Combine with hash map for subarray-sum-equals-k
    • 2D prefix sums work on matrices

    Interview questions

    Count subarrays with sum k?

    Store counts of prefix sums; add count[pre − k] at each step.

    More DSA topics

    ArraysLinked ListStackQueue