You are given an array that never changes and many queries asking for the sum between two indexes. How do you answer each query fast?

Build a prefix-sum array once. prefix[0] is 0 and prefix[i] is the sum of the first i numbers. The sum from left to right, both included, is prefix[right + 1] - prefix[left], which is one subtraction. Building takes O(n) time and O(n) memory, and every query is O(1). With q queries the total is O(n + q), against O(n times q) for adding the range up each time.

Count the contiguous subarrays of an integer array whose sum equals k. The array can contain negative numbers.

Keep a running total and a dictionary counting how many times each running total has appeared, starting with {0: 1} for the empty prefix. For each number, add it to the total. A stretch ending here sums to k when an earlier total equals total - k, so add that total's count to the answer, then record the current total. Time is O(n) on average and memory is O(n). It works with negative numbers because it never assumes the total only goes up.

You must add a value to every element in a range, many times, then print the final array. How do you avoid O(n) per update?

Use a difference array d of length n + 1. To add v to positions l to r, do d[l] += v and d[r + 1] -= v, which is O(1) per update. After all updates, take a running total of d. That value is the total change at each position, so add it to the original array. With k updates the cost is O(k + n), against O(k times n) when each update loops over its range.

Find an index where the sum of the numbers to its left equals the sum of the numbers to its right (the pivot index).

Compute the total sum. Walk through the array keeping the running left sum. At index i the right sum is total - left - nums[i], so the pivot is where left equals that value. Return the first such index, or -1. It takes two passes, O(n) time, and O(1) extra memory because a running total replaces the full prefix array.

Prefix Sums and Difference Arrays

beginner · 30 min · Asked often · Last reviewed 29 Oct 2026 · by TheLearningLoop Team

Key takeaways

A prefix-sum array stores the running total, so the sum of any range is one subtraction, prefix[right + 1] - prefix[left], after an O(n) build.
To count subarrays that add up to k, keep a dictionary of how often each running total has appeared. It works with negative numbers, where a sliding window does not.
A difference array is the reverse of a prefix sum. To add a value to a whole range, change just two slots, then take a running total at the end.
Prefix sums spend O(n) memory to turn repeated O(n) range queries into O(1).

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use prefix sums

Use prefix sums when you have:

Many range-sum queries on data that does not change: "what is the total sales from day 12 to day 40?"
A question about contiguous stretches that add up to a target: "how many subarrays sum to k?", especially with negative numbers.
A running total that you need at every position, such as a balance after each transaction.
Many range updates ("add 5 to every item from index 3 to 90") followed by one read of the final array. For that, use the reverse tool: a difference array.

Use something else when:

The data changes between queries: a prefix array goes stale after every update. Use a Fenwick tree or segment tree.
You only need one answer: a single loop is O(n) and needs no extra memory.
The numbers are all positive and you need a stretch with an exact or bounded total: a sliding window uses O(1) memory.
You want the maximum or minimum of a range: use a sparse table, segment tree or monotonic queue. Prefix sums only work for operations you can subtract, like addition.

There is no library to import for the core idea. A few languages have a running-total helper (see the real-world section), but a prefix array is a single loop.

How prefix sums work

A prefix sum is the total of the first i numbers. Store every one of them in an array once, and any range total is a subtraction.

prefix[0] = 0, and prefix[i] = prefix[i - 1] + nums[i - 1]. The sum from left to right (both included) is prefix[right + 1] - prefix[left].

Why the subtraction works: prefix[right + 1] adds up everything up to right. prefix[left] adds up everything before left. Taking one from the other leaves exactly the range. The array has one extra slot at the front, a 0, so a range that starts at index 0 needs no special case.

Two more ideas build on it:

Subarray sum equals k. A stretch ending at the current number sums to k when the running total now, minus some earlier running total, equals k. So keep a dictionary of how often each running total has appeared, and look up total - k. Start it with {0: 1} so stretches that begin at the start are counted. This works with negative numbers, where a sliding window breaks.
Difference arrays. This is the reverse of a prefix sum. To add v to every item from l to r, do d[l] += v and d[r + 1] -= v: only two slots change. After all updates, take a running total of d to get how much each position changed.

Try it

Pick one of the three techniques, then press Run and step through. The top row is your array and the bottom row is the helper array.

Prefix sums and difference arrays

Step 1 of 8 · Press Space to play, arrow keys to step

Examples:

Array

Prefix sums (prefix[i] = sum of the first i numbers)

The task: answer "what is the sum from index 1 to 4?" quickly, even for many queries. First build the prefix sums in one pass.

additions to build:: 0
work per query:: -

Once the prefix sums are built, each range query is a single subtraction. The brute-force count shows how many additions it would take to add the range up each time.

Speed

Things to try:

Range sum queries, "Sum of 1 to 4": for 1 4 2 5 3 6 the prefix array becomes 0 1 5 7 12 15 21 after 6 additions. The sum of indexes 1 to 4 is prefix[5] - prefix[1] = 15 - 1 = 14, one subtraction. Adding the range directly would take 4 additions every time.
Subarrays that add up to k, "k = 7": for 3 4 7 2 -3 1 4 2 the dictionary finds 4 stretches in one pass. Try "Negative numbers" (1 -1 1 -1 1 with k = 0): there are 6 stretches, and a sliding window could not find them.
Range updates, "Two updates": for 5 5 5 5 5 5, adding 2 to indexes 1 to 3 and subtracting 1 from indexes 2 to 5 changes only 4 slots in the difference array. Looping over the ranges would change 7 items. The final array is 5 7 6 6 4 4.

Prefix sum operations

Build the prefix array. Start with prefix = [0]. For each number, append prefix[-1] + number. One pass.

Answer a range query. Return prefix[right + 1] - prefix[left].

Count subarrays that sum to k.

Start with total = 0, count = 0 and a dictionary {0: 1}.
For each number, add it to total.
Add the dictionary's count for total - k to count.
Add one to the dictionary's count for total.

Apply range updates with a difference array.

Make d with n + 1 zeros.
For each update (l, r, v), do d[l] += v and d[r + 1] -= v.
Take a running total of d. Add it to the original array.

Interview fact. Prefix sums trade O(n) memory for turning every range query from O(n) into O(1). The dictionary trick turns an O(n²) "all subarrays" check into O(n).

Prefix sum time complexity

Operation	Time	Extra memory
Build the prefix array	O(n)	O(n)
One range-sum query	O(1)	O(1)
Count subarrays that sum to `k`	O(n) on average	O(n) for the dictionary
One range update (difference array)	O(1)	O(1)
Read the array after `u` updates	O(n + u)	O(n)

The dictionary version is O(n) on average because a hash table lookup is O(1) on average. In the unlucky worst case, where many keys land in the same bucket, it can slow down.

Prefix sums vs other approaches

n is the array length and q is the number of queries.

What you need	Prefix sums	Add the range each time	Sliding window	Fenwick or segment tree
Many range sums, data fixed	O(n + q)	O(n times q)	Not applicable	O(n + q log n)
Range sums while data changes	O(n) per update	O(n) per query	Not applicable	O(log n) per update and query
Subarray sum equals `k` with negatives	O(n), O(n) memory	O(n²)	Does not work	Not needed
Subarray sum equals `k`, all positive	O(n), O(n) memory	O(n²)	O(n), O(1) memory	Not needed
Many range additions, one final read	O(n + u) (difference array)	O(n times u)	Not applicable	O(n + u log n)

The bold cells show where each wins. Prefix sums win on fixed data with many queries. They lose as soon as the data changes between queries, and for operations you cannot subtract, such as the maximum.

How to explain prefix sums in an interview

Say the idea in one line: "I precompute running totals, so any range sum is one subtraction."
Explain the extra 0 at the front: "it makes the range from index 0 work without a special case".
For subarray sum equals k, say why the dictionary starts with {0: 1} and why it works with negatives: "it never assumes the total only grows".
State the trade: O(n) memory for O(1) queries, and name the fix when data changes: a Fenwick or segment tree.
Mention the 2D version: prefix sums over a grid answer any rectangle sum with four lookups.

Where you meet prefix sums in real systems

Any system that keeps asking "how much happened between these two points?" is using running totals. Three examples are drawn out below, the first with code you can run, then more.

Example 1: Sales totals between two days

A dashboard shows total sales for any date range a manager picks. Adding up the days in the range for every request would be slow for a year of data, so the system stores the running total of sales per day once. Any range is then one subtraction. The same code also counts how many stretches of days add up to a target, which answers questions such as "in how many periods did net sales equal exactly 7?". Open the example below to see the picture and the code.

Code: range sums and subarrays that add up to kTime O(n) build, O(1) per queryMemory O(n)

Sales for days 0 to 7 are 3, 1, 4, 1, 5, 9, 2 and 6. The running totals start with a 0. Sales from day 2 to day 5 are the total after day 5 (23) minus the total before day 2 (4), which is 19. Those two totals are highlighted.

Run on the eight daily values 3 1 4 1 5 9 2 6, all five versions build the totals 0 3 4 8 9 14 23 25 31 and report 19 for days 2 to 5 and 31 for all eight days. Run on 3 4 7 2 -3 1 4 2 with k = 7, all five count 4 stretches. The Java code uses long for totals so large sums do not overflow. The C++ code builds with -std=c++17.

def build_prefix(values):
    """prefix[i] is the sum of the first i values, so prefix[0] is 0.

    Time:   O(n). One pass, one addition per value.
    Memory: O(n). One extra number per value (plus the leading 0).
    """
    prefix = [0]
    for v in values:
        prefix.append(prefix[-1] + v)
    return prefix


def range_sum(prefix, left, right):
    """Sum of values[left..right] (both ends included), in constant time.

    prefix[right + 1] adds up everything up to `right`. Subtracting prefix[left]
    removes everything before `left`, leaving exactly the range.

    Time:   O(1). One subtraction, however long the range is.
    Memory: O(1).
    """
    return prefix[right + 1] - prefix[left]


def count_subarrays_with_sum(values, k):
    """How many contiguous stretches of `values` add up to k. Works with negative numbers.

    A stretch ending here sums to k when (running total now) - (a running total seen
    earlier) equals k. A dict counts how often each running total has appeared.

    Time:   O(n) on average. One dict lookup and one update per value.
    Memory: O(n). In the worst case the dict holds every running total.
    """
    seen = {0: 1}                      # the empty prefix has total 0
    total = 0
    count = 0
    for v in values:
        total += v
        count += seen.get(total - k, 0)          # earlier totals that leave a stretch of k
        seen[total] = seen.get(total, 0) + 1
    return count

Example 2: A bank statement

A bank stores each transaction once and shows the balance after every one. The balance on any date is the running total of all transactions up to it. The amount spent between two dates is the difference of two balances, so the statement never re-adds old transactions.

Four transactions of +100, -30, +50 and -20 give balances of 100, 70, 120 and 100. The net effect of the last three transactions (-30, +50, -20) is the final balance minus the first balance: 100 - 100 = 0. Two balances are enough, with no need to re-add the transactions.

Example 3: Hotel bookings with a difference array

A hotel system receives bookings such as "room from night 1 to night 3". Counting rooms taken per night by looping over every night of every booking is slow for long stays. A difference array adds one at the arrival night and subtracts one the night after departure, so each booking is two changes. A single running total at the end gives the number of rooms taken on each night.

Booking A covers nights 1 to 3 and booking B covers nights 2 to 5. The difference row shows +1 at nights 1 and 2 and -1 at nights 4 and 6. Its running total gives 0, 1, 2, 2, 1, 1 rooms for nights 0 to 5, with nights 2 and 3 the busiest.

More real-world scenarios

4. Image processing

An integral image is a two-dimensional prefix sum. Once it is built, the sum of the pixels in any rectangle takes four lookups, which makes blur filters and the face detector of Viola and Jones fast at any rectangle size.

5. Database running totals

SQL window functions such as SUM(amount) OVER (ORDER BY day) compute a running total for every row. That is a prefix sum, and reports like "year to date" are built on it.

6. Analytics dashboards

A dashboard that shows "visitors between 9am and 11am" keeps cumulative counts per minute or hour, so any time range is a subtraction instead of a scan of every event.

7. Weighted random choice

To pick an item at random in proportion to its weight, a system builds the prefix sums of the weights, draws a random number up to the total, and finds the first prefix sum that exceeds it with a binary search.

8. Parallel computing

A prefix sum is known as a scan in parallel programming, and it is a basic building block for GPU algorithms such as sorting and stream compaction. It looks sequential, yet there are parallel versions that finish in a logarithmic number of rounds.

9. Network counters

Routers and servers expose cumulative counters, such as total bytes sent. A monitoring tool turns them into a rate by subtracting two readings and dividing by the time between them, which is the same subtraction as a range sum.

10. Calendars and capacity planning

Meeting-room and airline-seat systems count overlapping reservations with a difference array: add one at the start, subtract one after the end, then take a running total to see the busiest moment and whether capacity is exceeded.

Language standard libraries

Some languages give you a running-total helper. Others expect a simple loop.

Language	Structure or class	What it is under the hood	Notes
Java	`Arrays.parallelPrefix`	In-place parallel prefix over an array	Works on `int[]`, `long[]` and `double[]` with an operator. It changes the array, so copy first if you need the original.
C++	`std::partial_sum`, `std::inclusive_scan`	Algorithms in `<numeric>`	`partial_sum` writes the running totals of a range. `inclusive_scan` is the C++17 version that may run in parallel.
C#	None built in	A loop or LINQ `Aggregate`	There is no running-total method in LINQ, so write the loop.
Rust	`Iterator::scan`	Iterator adapter that carries state	`scan` keeps a running total and yields it for each item.
Python	`itertools.accumulate`	Lazy iterator of running totals	`list(accumulate(nums))` gives the totals without the leading 0. NumPy offers `cumsum`.
Go	None in the standard library	A loop	Write the loop. It is short.
JavaScript	None built in	A loop or `reduce`	Use a loop. Building with `reduce` and spreading creates copies and gets slow.
Kotlin	`runningFold`, `runningReduce`, `scan`	Extension functions on collections	`runningFold(0) { a, b -> a + b }` returns the totals with a leading 0.

The pattern: the helper gives you the running totals, but you still need to add the leading 0 yourself in most languages, and the range query is always your own subtraction.

The takeaway

Whenever a system must answer many questions about the total between two points on data that rarely changes, look for prefix sums. When it must apply many range changes and read the result once, it usually uses a difference array. When the data changes between questions, it usually uses a Fenwick or segment tree instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
You are given an array that never changes and many queries asking for the sum between two indexes. How do you answer each query fast?
easy
2.
Count the contiguous subarrays of an integer array whose sum equals k. The array can contain negative numbers.
medium
3.
You must add a value to every element in a range, many times, then print the final array. How do you avoid O(n) per update?
medium
4.
Find an index where the sum of the numbers to its left equals the sum of the numbers to its right (the pivot index).
easy

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Fast and Slow Pointers

Monotonic Stack and Queue

Topics:Prefix sumDifference arrayRange sum querySubarray sum equals kCumulative sumRange update