Range Sum Query

Q: What is a prefix sum array?

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 then the sum of any range [left, right] is prefix[right+1] - prefix[left] .

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, O(n·q) in total.

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) .

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 18, the last two values to 1 + 8 = 9, index 0 alone to 2, and indexes 1 to 2 to 7 + 1 = 8.

Follow-up

If the numbers form a grid and each query asks for the sum of a rectangle, how would you extend prefix sums to answer each query in constant time?

Hints

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

0 of 3 opened

Solution

A single range is a loop, but every query can cover most of the array, so summing each one separately repeats the same additions. Add the array 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

For each query, add nums[left] through nums[right] into a total. It is correct because it reads every value in the range, and for one query that is the best you can do. A query can span up to n values, so q queries cost up to n × q additions: 1.5 × 10^7 when n = 10^4 and q = 1500, nearly all of them repeats.

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 [3, -2, 5, 1, -4, 6] that gives [0, 3, 1, 6, 7, 3, 9].

The range [left, right] is everything up to index right minus everything before index left: prefix[right+1] - prefix[left]. For [1, 4] that is prefix[5] - prefix[1] = 3 - 3 = 0. The leading 0 lets a range that starts at index 0 use the same formula. One pass of n additions builds the array, and each query is then one subtraction.

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

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 1.
Making prefix as long as nums, so prefix[i] includes nums[i]. A range starting at 0 then needs prefix[-1], which is out of bounds, and Python silently reads the last entry instead.
Stopping the brute force loop at i < right. Both ends are included, so [3, 3] would sum nothing.
In Lua and R, which count from 1, the 0-based query [left, right] covers nums[left+1] to nums[right+1], and the prefix indexes shift the same way.

Frequently asked questions3

What is a prefix sum array?

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 then the sum of any range [left, right] is prefix[right+1] - prefix[left].

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, O(n·q) in total.

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).

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

Test #1

Test #2

Arguments

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

Expected Output

[6, 0, 1]