JavaScript Coding Test Course, Calculating Interval Sum 2

Problem Description

The interval sum problem is one of the common types encountered in algorithm problems. In this lecture, we will address the second problem of calculating the interval sum. We will learn how to efficiently calculate the interval sum between two points in a given array.

Problem:
Given an integer array A and a query array queries, compute the interval sum from the l-th to the r-th index of array A for each query (l, r).

The array indexing starts from 0, the size of the array is N, and the number of queries is Q.

Input Format

1. The first line contains the size of the array A, N (1 ≤ N ≤ 106).

2. The second line contains the elements of array A. (A[i] is an integer, -109 ≤ A[i] ≤ 109)

3. The third line contains the number of queries Q (1 ≤ Q ≤ 105).

4. The next Q lines contain each query (l, r). (0 ≤ l ≤ r < N)

Output Format

For each query, output the interval sum on a new line.

Example

    Input:
    5
    1 2 3 4 5
    3
    0 2
    1 4
    2 2

    Output:
    6
    14
    3

Solution Process

The first step to efficiently obtain the interval sum is to create a prefix sum array. The prefix sum array stores the sum of the elements up to each index in the array, allowing us to calculate the interval sum in O(1) time.

Creating the Prefix Sum Array

The prefix sum array prefix is defined as follows:

prefix[0] = A[0],

prefix[i] = prefix[i-1] + A[i] (for 1 ≤ i < N)

With this prefix sum array, the interval sum A[l] + ... + A[r] can be calculated as follows:

sum(l, r) = prefix[r] - prefix[l - 1] (provided l > 0)

In the case where l = 0, we handle it as sum(0, r) = prefix[r].

Implementation

Now, let’s write the code to create the prefix sum array and calculate the interval sum for each query. Below is the implementation in JavaScript: 

    
    function rangeSum(A, queries) {
        const N = A.length;
        const prefix = new Array(N);
        prefix[0] = A[0];
        
        // Create the prefix sum array
        for (let i = 1; i < N; i++) {
            prefix[i] = prefix[i - 1] + A[i];
        }

        const result = [];
        // Process queries
        for (const [l, r] of queries) {
            if (l === 0) {
                result.push(prefix[r]);
            } else {
                result.push(prefix[r] - prefix[l - 1]);
            }
        }

        return result;
    }

    // Example input
    const A = [1, 2, 3, 4, 5];
    const queries = [[0, 2], [1, 4], [2, 2]];
    console.log(rangeSum(A, queries)); // [6, 14, 3]

Time Complexity Analysis

Creating the prefix sum array takes O(N) time, and each query can be processed in O(1). Therefore, the overall time complexity of the algorithm is O(N + Q). This is an efficient solution that satisfies the input conditions of the given problem.

Conclusion

In this lecture, we learned how to calculate the interval sum. We learned to use the prefix sum array to compute the interval sum in O(1) time. This approach can also be applied to solving other similar problems, which will be very helpful in studying algorithms.