Range Sum Query

Q: What is a prefix sum array?

It is an array where each entry is the total of all values before a position: prefix[i] = nums[0] + ... + nums[i-1] , with prefix[0] = 0 . You build it in one pass, and after that the sum of any range [left, right] is prefix[right+1] - prefix[left] , one subtraction.

Q: What is the time complexity of range sum queries with prefix sums?

O(n) to build the prefix array once, then O(1) per query, so O(n + q) for q queries. Adding up every range directly costs up to O(n) per query, which is O(n·q) in total.

Q: Why does the prefix array have one more entry than nums?

The extra prefix[0] = 0 stands for the empty start of the array. With it, every range uses the same formula, including ranges that start at index 0: prefix[right+1] - prefix[0] . Without it, you need a separate branch for left = 0 .

Q: What if the array can change between queries?

Then a prefix array is the wrong tool, because one update shifts every total after it and costs O(n) to repair. A Fenwick tree or a segment tree handles both an update and a range sum in O(log n) . When the array never changes, plain prefix sums are faster and shorter.

EasyPrefix sum

+10

You get an array of integers nums that never changes and a list of queries. Each query is a pair [left, right] of 0-based indexes, and it asks for nums[left] + nums[left+1] + ... + nums[right], both ends included. Return the answers in the same order as the queries.

Function

sumRange(nums: integer-array, queries: integer-2d-array) → integer-array

numsinteger-array: the array of integers, the same for every query
queriesinteger-2d-array: the ranges to add up, each a pair [left, right] with left ≤ right
Returnsinteger-array: the sum of each range, one per query, in query order

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ queries.length ≤ 1500
0 ≤ left ≤ right < nums.length for every query [left, right]

Examples

Input: nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
Output: [6, 0, 1]
Explanation: Indexes 0 to 2 hold 3 + (-2) + 5 = 6. Indexes 1 to 4 hold -2 + 5 + 1 + (-4) = 0. The range [3, 3] is the single value 1.

Input: nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
Output: [18, 9, 2, 8]
Explanation: The whole array adds up to 2 + 7 + 1 + 8 = 18, the last two values to 1 + 8 = 9, index 0 alone to 2 and indexes 1 to 2 to 7 + 1 = 8.

+14 hidden tests on Submit

Follow-up

Now the numbers form a grid, and each query asks for the sum of a rectangle given by two corners. How would you extend prefix sums to answer each query with a constant number of operations?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

One range is a loop. The problem is the number of them: every query can cover most of the array, so adding each one up separately repeats the same additions over and over. Add everything up once into prefix sums, and every range becomes one subtraction.

Add up each range

Correct, but does not finish on the largest tests

Intuition

Answer each query on its own: start a total at 0, add nums[left] through nums[right], and store the result. For [1, 4] in [3, -2, 5, 1, -4, 6] that is -2 + 5 + 1 + (-4) = 0.

It is correct, and for a single query it is the best you can do: you have to read every value in the range once. The cost is in the repetition. A query can span up to n values, so q queries cost up to n × q additions. With n = 10^4 and 1500 queries that each cover most of the array, that is about 1.3 × 10^7 additions, nearly all of them repeats of work done for an earlier query.

Besides the answer list, it keeps one total, so the extra space is O(1).

Algorithm

Create an empty answer list.
For each query [left, right], set total = 0.
Add nums[i] to total for every i from left to right, both included.
Append total to the answers, and return them after the last query.

def sumRange(nums, queries):
    answers = []
    for left, right in queries:
        total = 0
        for i in range(left, right + 1):
            total += nums[i]
        answers.append(total)
    return answers

Prefix sums

Intuition

Let prefix[i] be the sum of the first i values, with prefix[0] = 0 for the empty start. For [3, -2, 5, 1, -4, 6] that gives prefix = [0, 3, 1, 6, 7, 3, 9]. Each entry is the one before it plus one value, so the whole array takes n additions.

The range [left, right] is everything up to and including index right, minus everything before index left. That is prefix[right+1] - prefix[left]. For [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. For [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. The leading 0 is what makes a range that starts at index 0 work without a special case.

Building the array costs O(n), and each query then costs one subtraction, so the total is O(n + q) time and O(n) extra space. No prefix sum here passes 10^4 × 10^4 = 10^8 in size, so 32-bit integers are enough.

Algorithm

Create prefix of length n+1 with prefix[0] = 0.
For each i from 0 to n-1, set prefix[i+1] = prefix[i] + nums[i].
For each query [left, right], append prefix[right+1] - prefix[left] to the answers.
Return the answers.

def sumRange(nums, queries):
    # prefix[i] is the sum of the first i values, so prefix[0] = 0.
    prefix = [0] * (len(nums) + 1)
    for i, value in enumerate(nums):
        prefix[i + 1] = prefix[i] + value
    # nums[left..right] is the first right+1 values minus the first left values.
    return [prefix[right + 1] - prefix[left] for left, right in queries]

Pitfalls and edge cases

Almost every bug here is an index that is off by one.

Writing prefix[right] - prefix[left]. With prefix[0] = 0 that leaves out nums[right], so the range [3, 3] comes back as 0 instead of the value at index 3.
Building prefix with the same length as nums, so prefix[i] includes nums[i]. Then a range starting at 0 needs prefix[left-1], which is out of bounds, and in Python silently reads the last entry. The extra leading 0 removes that special case.
Stopping the brute force at i < right. Both ends of the range are included.
Forgetting that Lua and R count from 1. The 0-based query [left, right] covers nums[left+1] to nums[right+1] there, and the prefix difference shifts the same way.
Using a 32-bit total when values or lengths grow. Here the largest sum is 10^8, but with values near 10^9 a prefix sum overflows quickly, and a 64-bit array is the safe default.

Frequently asked questions4

What is a prefix sum array?

It is an array where each entry is the total of all values before a position: prefix[i] = nums[0] + ... + nums[i-1], with prefix[0] = 0. You build it in one pass, and after that the sum of any range [left, right] is prefix[right+1] - prefix[left], one subtraction.

What is the time complexity of range sum queries with prefix sums?

O(n) to build the prefix array once, then O(1) per query, so O(n + q) for q queries. Adding up every range directly costs up to O(n) per query, which is O(n·q) in total.

Why does the prefix array have one more entry than nums?

The extra prefix[0] = 0 stands for the empty start of the array. With it, every range uses the same formula, including ranges that start at index 0: prefix[right+1] - prefix[0]. Without it, you need a separate branch for left = 0.

What if the array can change between queries?

Then a prefix array is the wrong tool, because one update shifts every total after it and costs O(n) to repair. A Fenwick tree or a segment tree handles both an update and a range sum in O(log n). When the array never changes, plain prefix sums are faster and shorter.

Python

def sumRange(nums, queries):
    # Write code here

Test cases

Case 1

Case 2

Input

nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3]]

Expected

[6, 0, 1]