Prefix Sum

DSA · Arrays and Searching

Theory

A prefix sum array stores, at each position i, the total of all elements before it. After building it once in O(n), the sum of any range [l, r] is prefix[r+1] - prefix[l], answered in O(1). Prefix sums generalise to counts, 2-D grids and, combined with a hash map, to counting subarrays with a given sum.

Why we use it

It answers many range-sum queries quickly without re-adding the same numbers each time.

When to use it

Use it when you need many range totals, running totals, or subarray-sum questions.

How it works

  1. Start: prefix[0] = 0
  2. For i = 1..n: prefix[i] = prefix[i-1] + arr[i-1]
  3. Query sum(l..r)
  4. Answer = prefix[r+1] - prefix[l]
  5. Each query in O(1)

Syntax

prefix[0] = 0
prefix[i+1] = prefix[i] + arr[i]
sum(l..r) = prefix[r+1] - prefix[l]

Build: O(n)   Each query: O(1)

Example

sales = [5, 3, 8, 6, 2, 7]
prefix = [0]
for s in sales:
    prefix.append(prefix[-1] + s)
print("Prefix:", prefix)

def range_sum(l, r):
    return prefix[r + 1] - prefix[l]

print("Days 1 to 3 total:", range_sum(1, 3))
print("Days 0 to 5 total:", range_sum(0, 5))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic