Sum at Even Positions Using Prefix Sum

You are given an array A with a length of N and Q queries represented by a 2D array B of size Q*2. Each query in the array B consists of two integers, B[i][0] and B[i][1], which define a range within the array A.

For each query, the task is to compute the sum of all elements located at even indices within the specified range A[B[i][0]…B[i][1]]. This means you need to iterate through the array A from the starting index B[i][0] to the ending index B[i][1], and add up the values of the elements that are positioned at even indices (i.e., indices 0, 2, 4, etc.).

The result for each query should be the total sum of these elements. This process needs to be repeated for all Q queries provided in the 2D array B.

Note: Use 0-based indexing.

Problem Constraints

1 <= N <= 10⁵
1 <= Q <= 10⁵
1 <= A[i] <= 100
0 <= B[i][0] <= B[i][1] < N

Input Format

First argument A is an array of integers.
Second argument B is a 2D array of integers.

Output Format

Return an array of integers.

Example Input

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

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

Example Output

Output 1: [4, 8]
Output 2: [10, 17]

Example Explanation

For input 1:
The subarray for the first query is [1, 2, 3] whose sum of even indices is 4.
The subarray for the second query is [2, 3, 4, 5] whose sum of even indices is 8.

For input 2:
The subarray for the first query is [2, 1, 8, 3] whose sum of even indices is 10.
The subarray for the second query is [8, 3, 9] whose sum of even indices is 17.

public class SumOfEvenIndices {

    public static int[] evenSum(int[] A, int[][] B) {
        int result[] = new int[A.length];
        int prefixSum = 0;
        // Create Prefix Sum array
        for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) { // Treat as event number and make sum as 1.
                prefixSum = A[i] + prefixSum;
                result[i] = prefixSum;
            } else {
                result[i] = prefixSum;
            }

        }

        int output[] = new int[B.length];
        for (int j = 0; j < B.length; j++) {
            int startIndex = B[j][0];
            int endIndex = B[j][1];
            if (startIndex == 0) {
                output[j] = result[endIndex];
            } else {
                output[j] = result[endIndex] - result[startIndex - 1];
            }
        }
        return output;
    }

}

Code Breakdown and Explanation

javaCopy codepublic class SumOfEvenIndices {
    public static int[] evenSum(int[] A, int[][] B) {
        int result[] = new int[A.length];
        int prefixSum = 0;

evenSum Method:
- Takes two arguments:
  - int[] A: The input array containing integers.
  - int[][] B: A 2D array where each row represents a range [startIndex, endIndex].
- Output: An integer array where each element represents the sum of elements at even indices within the corresponding range specified in B.
- Variables:
  - result[]: This array will store the cumulative sum of elements at even indices up to each index in A.
  - prefixSum: A running sum used to keep track of the cumulative sum of elements at even indices encountered so far.

1. Constructing the Even Index Prefix Sum Array:

for (int i = 0; i < A.length; i++) {
            if (i % 2 == 0) { // Check if index is even
                prefixSum = A[i] + prefixSum;
                result[i] = prefixSum;
            } else {
                result[i] = prefixSum;
            }
        }

for loop: Iterates over the array A.
- Condition if (i % 2 == 0):
  - Checks if the current index i is even. If it is, the prefixSum is updated by adding A[i] to it.
  - result[i] = prefixSum;: Stores the updated cumulative sum of elements at even indices up to index i in result[i].
- else block:
  - If the index i is odd, prefixSum remains unchanged, and result[i] is set to the current prefixSum.
result[] array: By the end of this loop, result[i] contains the sum of elements at even indices from the start of the array up to index i.

Processing Range Queries:

int output[] = new int[B.length];

        for (int j = 0; j < B.length; j++) {
            int startIndex = B[j][0];
            int endIndex = B[j][1];
            if (startIndex == 0) {
                output[j] = result[endIndex];
            } else {
                output[j] = result[endIndex] - result[startIndex - 1];
            }
        }

        return output;
    }
}

output[]: This array will store the sum of elements at even indices for each range specified in B.
for loop: Iterates over the 2D array B to process each range [startIndex, endIndex].
- Extract startIndex and endIndex:
  - For each query j, startIndex = B[j][0] and endIndex = B[j][1] represent the start and end indices of the current range.
- Condition if (startIndex == 0):
  - If the startIndex is 0, the sum of elements at even indices from the start of the array to endIndex is simply result[endIndex].
- else block:
  - If startIndex is not 0, the sum of elements at even indices between startIndex and endIndex is calculated by subtracting result[startIndex - 1] from result[endIndex]. This operation effectively removes the sum of elements at even indices before startIndex.
Return Statement:
- The method returns the output[] array, which contains the sum of elements at even indices for each range in B.

Summary:

Prefix Sum Array (result[]):
- The array result[] is used to store the cumulative sum of elements at even indices up to each index in A.
Range Query Calculation:
- For each range [startIndex, endIndex], the sum of elements at even indices in that range is efficiently calculated using the result[] array.
Efficiency:
- This approach allows for efficient querying of the sum of elements at even indices in any given range after an initial O(n) preprocessing step, making the range queries O(1) for each query.

This method is particularly useful when you have multiple range queries on the same array, as it reduces the time complexity of each query to constant time.