Step-by-Step Guide to Range Sum Query on Leetcode

Problem Description

You are provided with an integer array A of length N.
Additionally, you have a 2D integer array B with dimensions M x 2, where each row represents a [L, R] query.
For each query, your task is to determine the sum of all elements from indices L to R in array A (0-indexed).
In other words, for each query, compute the sum A[L] + A[L + 1] + A[L + 2] +... + A[R - 1] + A[R].

Problem Constraints

1 <= N, M <= 10⁵
1 <= A[i] <= 10⁹
0 <= L <= R < N

Input Format

The first argument is the integer array A.
The second argument is the 2D integer array B.

Output Format

Return an integer array of length M where i^th element is the answer for i^th query in B.

Example Input

Input 1:
A = [1, 2, 3, 4, 5]
B = [[0, 3], [1, 2]]

Input 2:
A = [2, 2, 2]
B = [[0, 0], [1, 2]]

Example Output

Output 1:
[10, 5]

Output 2:
[2, 4]

Example Explanation

Explanation 1:
The sum of all elements of A[0 ... 3] = 1 + 2 + 3 + 4 = 10.
The sum of all elements of A[1 ... 2] = 2 + 3 = 5.

Explanation 2:

The sum of all elements of A[0 ... 0] = 2 = 2.
The sum of all elements of A[1 ... 2] = 2 + 2 = 4.

Approach 1: Brut force approach with Time complexity O(n^2)

public class PrefixSumProblem {
    public static long[] rangeSum(int[] A, int[][] B) {

        long result[] = new long[B.length];

        for(int i=0;i<B.length;i++){
            int tempSum = 0;
            for(int j=B[i][0];j<=B[i][1];j++){
                tempSum = tempSum + A[j];
            }
            result[i] = tempSum;
        }

        return result;
    }
    public static void main(String args[]){
        int array[] = {1,2,3,4,5};
        int queries[][] = {{0,3},{1,2}};
        PrefixSumProblem1.rangeSum(array, queries);
    }
}

Time complexity: O(n^2)

Space complexity: O(n)

Prefix Sum Technique

The Prefix Sum technique is a widely-used and efficient method for addressing array-related problems in Data Structures and Algorithms (DSA). The core concept of the prefix sum is to preprocess the array so that each element at index i in the prefix sum array represents the cumulative sum of all elements from the beginning of the original array up to index i. This preprocessing enables rapid calculation of the sum of any subarray in constant time.

How It Works

Given an array arr of size n, the prefix sum array prefix_sum is defined as:

prefix_sum[i]=arr[0]+arr[1]+⋯+arr[i]

Steps to Create a Prefix Sum Array:

1. Initialize the Prefix Sum Array:

   • Create an array prefix_sum of the same size as arr.

2. Calculate Prefix Sums:

   • The first element of prefix_sum is the same as the first element of arr.

   • For each subsequent element, the prefix sum at index i is calculated as: prefix_sum[i]=prefix_sum[i−1]+arr[i]

Applications

1. Range Sum Queries: Efficiently determine the sum of elements between indices i and j:

   [ \text{sum}(i, j) = \text{prefix_sum}[j] - \text{prefix_sum}[i-1] ]

2. Finding Equilibrium Index: Identify an index where the sum of elements on the left equals the sum on the right.

3. Counting Subarrays with Given Sum: Utilize a hashmap or similar data structure to store the prefix sums, enabling the count of subarrays that sum to a specific value.

4. 2D Prefix Sum: Apply the prefix sum concept to 2D arrays for efficient submatrix sum queries.

Complexity

• Time Complexity: Constructing the prefix sum array takes O(n) time.

• Space Complexity: The prefix sum array requires O(n) additional space.

This technique is particularly advantageous in scenarios where multiple range sum queries are required on the same array, as it reduces the time complexity of each query to O(1).

Approach 2: Using Prefix Sum

public class Solution {
    public long[] rangeSum(int[] A, int[][] B) {
       long prefixSum[] = new long[A.length];
        prefixSum[0] = A[0];
        for(int i=1;i<A.length;i++){
            prefixSum[i] = prefixSum[i-1]+A[i];            
        }
        long result[] = new long[B.length];
        for(int j=0;j<B.length;j++){
            int startIndex = B[j][0];
            int endIndex = B[j][1];
            if(startIndex == 0){
                result[j] = prefixSum[endIndex];
            }else{
                result[j] = prefixSum[endIndex]- prefixSum[startIndex-1];
            }            
        }
        return result;
    }
}

Explanation

• The code computes the prefix sum of an array A, enabling efficient calculation of the sum of elements over any subarray.

• It processes a list of range queries in B, where each query specifies a range of indices in A.

• Utilizing the prefix sum array, it efficiently computes and stores the sum for each range in the result array, which is subsequently returned.

This approach ensures that each range sum query can be answered in constant time after the initial prefix sum array is computed in linear time.

This article addresses the problem of efficiently computing range sums for multiple queries on an integer array. It contrasts the brute-force approach with the prefix sum technique, highlighting the significant performance improvements achievable with the latter. The prefix sum technique preprocesses the array to create a cumulative sum array, enabling constant-time subarray sum calculations after an initial linear-time setup. Detailed code examples and explanations are provided for both approaches.