Skip to main content

Prefix Sum

Learn Prefix Sum (Arrays, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is a Prefix Sum? A prefix sum array pre stores running totals: pre[i] = arr[0] + arr[1] + ... + arr[i] . Once built (O(n) once), the sum of ANY range [l, r] can be answered in O(1) instead of O(n): sum(0, r) = pre[r] sum(l, r) = pre[r] - pre[l - 1] (for l > 0) This is the single biggest win of prefix sums: many range-sum queries, each O(1), after one O(n) precomputation.

More lessons in Arrays