In DSA, some of the most elegant solutions come from simple ideas applied smartly. One such gem is Prefix Sum — a concept that can turn a brute force problem into an efficient one-liner.
Think of prefix sum like a running total that saves you from recalculating the same work again and again.
Why Prefix Sum Matters
Imagine you have an array of numbers and you’re repeatedly asked:
What’s the sum of elements between index L and R?
The naïve way would be looping from L to R every single time — O(n) per query. But what if you had already stored the total up to every point? Then answering each query becomes O(1). That’s the magic of prefix sums.
Real-World Example
Let’s say you’re analyzing daily sales data over a year.
- Without prefix sum: every time you want to know total sales between Day 20 and Day 200, you loop and add 180 values.
- With prefix sum: you just do
prefix[200] - prefix[19]. Instant.
This idea is used everywhere — from analytics dashboards and stock trend calculations to optimizing subarray problems in competitive programming.
How It Works — Pseudocode
Given array arr[0..n-1]
Let prefix[0] = arr[0]
For i from 1 to n-1:
prefix[i] = prefix[i-1] + arr[i]
Now, the sum of elements from L to R can be found in constant time:
if L == 0:
range_sum = prefix[R]
else:
range_sum = prefix[R] - prefix[L-1]
Why You Should Learn This Early
Prefix sum isn’t just another trick — it’s a building block. Once you master it, problems like “range sum queries,” “subarray sums,” or even some “difference array” techniques become intuitive. It also forms the foundation for 2D prefix sums (think image processing, matrix problems, heatmaps, etc.).
Explore a Real Problem
In my detailed Medium article, I’ve explained how to use this concept to find the sum of elements in a given range, step by step with a practical example and code.
Read it here
Learning prefix sum once can save you countless loops in future problems.
If you’re diving into DSA, this is one of those must-know techniques that will keep coming back in interviews and contests.