EasyDSA10 min read

What is the prefix sum technique?

Q: What is the prefix sum technique?

**Target Audience:** Beginners preparing for coding interviews — you should know arrays and loops. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown in the **Verified** section was produced by actually running the Python code with `python3 main.py`; nothing is quoted from memory. ## 1. Why This Even Matters — A Story First Think of a car odometer. If it read 1,200 km when you left home and 1,550 km when you arrived, you drove 350 km — you did not need to add up every kilometre of the trip, you just subtracted two readings. A prefix sum is an odometer for an array: for every position it stores "total so far". Then the sum of any stretch of the array is just one reading minus another. The trade is simple: spend one pass, O(n), writing down the running totals, and afterwards every "sum from index `l` to

1.2k views

2 of 154

The problem

Question presented to candidate: "What is the prefix sum technique? Explain it, then write Python code that preprocesses a list so that any range-sum query takes constant time."

What a strong answer should cover:

Definition: prefix[i] is the sum of the first i elements; with a leading 0, the range l..r is prefix[r + 1] - prefix[l].
Cost: O(n) to build, O(1) per query; O(n + q) instead of O(n·q) for q queries.
When to use it (static array, subarray-sum problems) and when not (frequent updates: Fenwick or segment tree).
Extensions: 2D prefix sums with inclusion-exclusion; difference arrays for range updates.
Python specifics: itertools.accumulate (with initial=0), list comprehensions for 2D tables, ints never overflow.

Code / implementation expected: Yes — build and query functions in Python.

dsa
prefix-sum
arrays

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know arrays and loops. Difficulty: Easy Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown in the Verified section was produced by actually running the Python code with python3 main.py; nothing is quoted from memory.

1. Why This Even Matters — A Story First

Think of a car odometer. If it read 1,200 km when you left home and 1,550 km when you arrived, you drove 350 km — you did not need to add up every kilometre of the trip, you just subtracted two readings. A prefix sum is an odometer for an array: for every position it stores "total so far". Then the sum of any stretch of the array is just one reading minus another.

The trade is simple

The solution is hidden so you can try first

10 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBuild a prefix array and answer range queries

Practice

Python2D prefix sums for rectangle queries

Practice

PythonDifference array for range updates

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

No comments yet. Share how you would answer it.

Question 2 of 154 in DSA

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All DSA questions

Up nextEasy→

How does binary search work and what are its requirements?

Continue