Prefix Sum Explained: Any Range Sum in 1 Step | Java DSA

Here's a question. You have an array of one million numbers. And someone asks you one million questions. Each question is: what's the sum from this position to that position?

If you add the numbers up again for every question, that's up to a million million steps. A trillion. Your program would run for hours.

But with one simple trick, every answer takes just one subtraction. The whole thing finishes in about two million steps. In under a second.

That trick is called the prefix sum. And by the end of this video, you'll be able to use it yourself.

Welcome back to Compiled Canvas. This is Episode Eight of our DSA series. Last time, we learned how arrays work. Today, we learn our first real array trick. And it's one of the easiest, and most useful, tricks in all of DSA.

Here's the plan. The problem we're solving. The slow way. A picture that makes the trick obvious. Building the prefix array. Answering any question in one step. Real Java code. The one mistake everyone makes. A cheat sheet. And an easy quiz at the end.

Let's go.

First, the problem.

Here's our array: two, four, one, three, five. Five numbers, at indexes zero to four.

The question is: what is the sum from index one to index three?

Let's look. Index one is four. Index two is one. Index three is three. Four plus one plus three is eight. So the answer is eight.

That's called a range sum. A range is just "from here to there". And range sum questions show up everywhere in coding interviews.

Now, the slow way. For every question, we loop from the start of the range to the end, and add as we go. For a short range, that's quick. But a range can cover the whole array. So one question can take n steps. That's O of n.

And if there are many questions, say q questions, the total work is n times q. With a million numbers and a million questions, that's the trillion steps we started with.

So we need a better idea. And the better idea comes from the road.

If you've ever travelled on a highway in India, you've seen the small kilometre stones on the side of the road. Each stone tells you how far you are from the start. Zero. Two. Six. Seven. Ten. Fifteen.

Now, here's a question. How far is it from the stone that says six, to the stone that says fifteen?

You don't measure the road again. You just subtract. Fifteen minus six is nine kilometres. One subtraction.

That's the whole trick. Each stone stores the total distance so far. And the distance between any two stones is just one subtraction.

The prefix sum does exactly the same thing, for an array.

Let's build the prefix array.

A prefix array stores the running total. Each box holds the sum of everything before it.

We'll make it one box longer than the original array. And we put a zero at the very start, just like the first kilometre stone at the start of the road.

Our array is two, four, one, three, five. Let's build it, step by step.

Box zero is zero. Nothing added yet.

Box one: zero plus two. Two.

Box two: two plus four. Six.

Box three: six plus one. Seven.

Box four: seven plus three. Ten.

Box five: ten plus five. Fifteen.

So the prefix array is: zero, two, six, seven, ten, fifteen. Look closely. Those are exactly the kilometre stones from our road.

Building it means visiting every number once. So building the prefix array is O of n. But we only build it once.

Now the magic part. Answering a question.

To get the sum from index L to index R, we take the prefix at R plus one, and subtract the prefix at L.

Let's try it. Sum from index one to index three. R plus one is four, and the prefix at four is ten. L is one, and the prefix at one is two. Ten minus two is eight.

And eight is exactly the answer we got by adding four, one and three. One subtraction instead of a loop.

Why does it work? The prefix at four is the total of the first four numbers: two, four, one and three. The prefix at one is the total of just the first number: two. Take away the two, and you're left with four, one and three. That's our range.

Let's do another one. The sum of the whole array, from index zero to index four. The prefix at five is fifteen. The prefix at zero is zero. Fifteen minus zero is fifteen. Check: two plus four plus one plus three plus five is fifteen. Correct.

One more. The sum from index two to index two. That's just one box. The prefix at three is seven. The prefix at two is six. Seven minus six is one. And the value at index two is one. Correct again.

Your turn. Pause the video and try this one. Using the prefix array zero, two, six, seven, ten, fifteen, what is the sum from index two to index four?

Ready? R plus one is five, and the prefix at five is fifteen. L is two, and the prefix at two is six. Fifteen minus six is nine. Check: one plus three plus five is nine. If you got nine, you've got it.

Look at this graph. Along the bottom is the length of the range. Up the side is the time to answer one question. The slow way is a line going up. The longer the range, the longer it takes. The prefix sum is a flat line. A range of five, or a range of five million, is still one subtraction.

Now look at this second graph. This one shows the total work as the number of questions grows. The slow way climbs steeply, because every question loops again. The prefix sum pays once to build, and then barely moves. That's the difference between hours and under a second.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now let's write it in Java.

First, we make the prefix array, one box bigger than the original: int array prefix, equals new int of n plus one. Every box starts at zero, so the first box is already zero.

Then one loop. For i from zero to n: prefix of i plus one equals prefix of i, plus arr of i. Each box is the box before it, plus the next number.

And to answer a question: return prefix of R plus one, minus prefix of L. That's it. One line.

So the whole technique is: one loop to build, and one subtraction per question.

Where would you use this in real life? Think of a shop that writes down its sales every day. The owner asks: how much did we sell from day ten to day twenty? Or a fitness app that counts your steps every day, and shows your total for this week. Build the running total once, and every "from here to there" question is one subtraction.

Now, the one mistake everyone makes.

It's the plus one. The sum from L to R is prefix of R plus one, minus prefix of L. Not prefix of R. Forget the plus one, and you'll leave out the last number of your range.

Here's an easy way to remember it. The prefix at any box is the total of everything before that box. So to include index R, you need the box after it. That's R plus one.

One more small tip. If the numbers are big, the running total can get too big for an int. In that case, use a long for the prefix array.

So, here's the whole prefix sum in one cheat sheet. Pause and screenshot this.

The prefix array is one box longer than the original, and starts with zero.

Each box is the box before it, plus the next number.

Building it: O of n, and you do it once.

The sum from L to R: prefix of R plus one, minus prefix of L.

Each question: O of one.

And watch out for the plus one, and use long for big numbers.

Okay, quiz time. Three easy questions. Pause the video, think, and then hit play.

Question one. The array is five, two, seven. What is its prefix array?

Question two. How long does it take to build the prefix array, and how long does each question take?

Question three. The prefix array is zero, three, eight, ten, sixteen. What is the sum from index one to index three?

Ready?

Question one: zero, five, seven, fourteen. Start with zero. Then zero plus five is five. Five plus two is seven. Seven plus seven is fourteen.

Question two: building takes O of n, because we visit every number once. Each question takes O of one, because it's one subtraction.

Question three: thirteen. R plus one is four, and the prefix at four is sixteen. The prefix at one is three. Sixteen minus three is thirteen.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. A range sum is the sum from one index to another. The slow way loops for every question, so it's O of n per question. The prefix array stores the running total, like kilometre stones on a highway. It starts with zero, and it's one box longer than the original array. The sum from L to R is prefix of R plus one, minus prefix of L. Build once in O of n, then answer every question in O of one.

Your homework. Solve Running Sum of 1d Array on LeetCode. It's building the prefix array, exactly like we did today. Then try Range Sum Query, Immutable. It's the exact problem from this video. And tell me in the comments: for the array one, two, three, four, what is the prefix array?

Next episode, we learn the two pointers technique. It's the trick you saw when we reversed an array, and it solves a whole family of problems, like finding a pair that adds up to a target, in just one pass.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.