Range Sum Query Using Prefix Sum — Problem Statement & Solution Guide
Problem Description
Given an array of integers points representing the points scored by a team in each match, implement a function to calculate the total points scored by the team in a given range of matches [left, right].
Examples
Input
[1, 2, 3, 4, 5, 6]
Output
14
Explanation: Step-by-step: Given the array [1, 2, 3, 4, 5, 6], we first calculate the prefix sum array. The prefix sum array would be [1, 3, 6, 10, 15, 21]. To calculate the sum of points from index 1 to 5, we use the formula: prefix_sum[right] - prefix_sum[left - 1] + sum(points[left:right+1]) = 21 - 3 + 2 + 3 + 4 = 14.
Input
[1, 3, 3, 4]
Output
10
Explanation: Step-by-step: Given the array [1, 3, 3, 4], we first calculate the prefix sum array. The prefix sum array would be [1, 4, 7, 11]. To calculate the sum of points from index 1 to 3, we use the formula: prefix_sum[right] - prefix_sum[left - 1] + sum(points[left:right+1]) = 7 - 4 + 3 + 4 = 10.
Constraints
- 1 <= points.length <= 10^5
- 0 <= left <= right < points.length
- -10^4 <= points[i] <= 10^4
- Multiple queries may be issued on the same array.
Optimal Approach & Strategy
Cumulative sum for range queries
Verified Code Solutions
public int rangeSumQuery(int[] points, int left, int right) {
int[] prefixSum = new int[points.length + 1];
for (int i = 0; i < points.length; i++) {
prefixSum[i + 1] = prefixSum[i] + points[i];
}
return prefixSum[right + 1] - prefixSum[left];
}def range_sum_query(points):
prefix_sum = [0] * (len(points) + 1)
for i in range(len(points)):
prefix_sum[i + 1] = prefix_sum[i] + points[i]
def query(left, right):
return prefix_sum[right + 1] - prefix_sum[left]
return queryAsked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.