C++ Coding Test Course, Finding Interval Sums 2

In this lecture, we will cover the second problem of calculating the range sum. The range sum problem is a very important topic in algorithms and data structures, and it is useful in various situations. We will learn how to efficiently calculate the sum of a given range using an algorithm.

Problem Description

Given an array as follows, there will be several pairs of starting and ending indices provided. Write a program to calculate the range sum for each pair.

Input

  • The first line contains the size of the array N (1 ≤ N ≤ 100,000) and the number of queries M (1 ≤ M ≤ 100,000).
  • The second line contains N integers that are the elements of the array. Each element’s value is between -10,000 and 10,000 inclusive.
  • Subsequently, M lines are given, each containing two integers S and E, which signify calculating the sum of the range [S, E]. (S, E use 1-based indexing.)

Output

Print the range sum for each query on a new line.

Problem Analysis

The problem of calculating the range sum is very inefficient, as directly calculating the sum results in a time complexity of O(N), making it O(N*M) when M is large. Therefore, in such cases, we can improve the calculation to O(1) using the prefix sum technique.

Algorithm

  1. Create a prefix sum array.
  2. For each query, use the start and end indices to calculate the range sum in O(1) time.

Implementation

Now let’s implement this algorithm in C++.


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> arr(N + 1, 0);
    vector<int> prefixSum(N + 1, 0);

    // Input the array
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        prefixSum[i] = prefixSum[i - 1] + arr[i]; // Calculate the prefix sum
    }

    // Processing queries
    for (int i = 0; i < M; i++) {
        int S, E;
        cin >> S >> E;
        // Calculate the range sum
        cout << prefixSum[E] - prefixSum[S - 1] << endl;
    }

    return 0;
}

Code Explanation

Each part of the code performs the following tasks:

  • Input: Read N and M, then read N numbers and save them in the array arr.
  • Create Prefix Sum Array: Generate a prefixSum array to calculate and store the sum up to the i-th element.
  • Process Queries: For each query, read S and E, and compute the range sum in O(1) time using the prefixSum.

Complexity Analysis

The time complexity of this algorithm is as follows:

  • Creating the prefix sum array: O(N)
  • Processing each query: O(M)
  • Total time complexity: O(N + M)

Conclusion

In this lecture, we learned an efficient way to calculate the range sum. By using the prefix sum technique, we were able to avoid explicit looping and significantly reduce the time complexity. This technique can be applied to many problems, so it is important to master it.

In the next lecture, we will cover more complex range sum problems using different data structures. Thank you!