You are given an integer array. You must process multiple range-sum queries of the form:
"Return the sum of elements from index left to right (inclusive)."
To make queries efficient, you must preprocess the array.
You will be given:
-
An array
nums -
Several queries asking for sum(left, right)
A common method is to build a prefix sum array, where:
prefix[i] = sum of nums[0…i-1]
Then:
sum(left, right) = prefix[right + 1] – prefix[left]
An integer array nums.
A list of queries, each with left and right indices.
For each query, output the sum of the subarray from nums[left] to nums[right].
Example 1
Input:
nums = [-2, 0, 3, -5, 2, -1]
Queries:
sum(0, 2)
sum(2, 5)
sum(0, 5)
Output:
1
-1
-3
Explanation:
sum(0,2) = -2 + 0 + 3 = 1
sum(2,5) = 3 - 5 + 2 - 1 = -1
sum(0,5) = total = -3
-
1 ≤ nums.length ≤ 10⁴
-
Queries may be many
-
-10⁵ ≤ nums[i] ≤ 10⁵
-
Precompute prefix sums
-
Answer queries in O(1) time
-
Remember right+1 and left indexing carefully
Prefix sums store cumulative totals:
prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
Range sum becomes a simple subtraction.
This makes repeated queries very fast.