C++ Coding Test Course, Range Sum

The range sum problem is an algorithm problem that efficiently calculates the sum of a specific range within a given array. This problem frequently appears in various programming languages, particularly with important implementations in C++. In this tutorial, we will set a specific problem for the range sum problem and explain the process to solve it in detail.

1. Problem Description

Let’s assume we are given an array composed of integers. The size of the integer array A is N. We need to calculate the sum of specific ranges in the array through M queries. The starting index of the range is provided as L, and the ending index is provided as R. We need to calculate A[L] + A[L+1] + ... + A[R].

For example, suppose the array A is as follows:

A = [10, 20, 30, 40, 50]

And let’s assume the following queries are given:

1. L = 1, R = 3
2. L = 0, R = 4
3. L = 2, R = 2

Calculating the range sum for the given queries yields the following results:

1. A[1] + A[2] + A[3] = 20 + 30 + 40 = 90
2. A[0] + A[1] + A[2] + A[3] + A[4] = 10 + 20 + 30 + 40 + 50 = 150
3. A[2] = 30

2. Problem Solving Approach

The traditional method to solve the range sum problem is to iterate through the array directly. However, this can be inefficient. For example, if each query among M queries spends O(R - L + 1) time, in the worst case, it will take O(N * M) time. To improve this, we can use the following method.

2.1. Preprocessing Method – Cumulative Sum Array

To quickly calculate the sum of all queries, we can utilize a cumulative sum array. First, we define the cumulative sum array S for the given array A. The cumulative sum array is calculated as follows:

S[i] = S[i - 1] + A[i]

Here, S[0] is initialized to 0. Using the cumulative sum array, the sum of a range can be calculated easily as follows:

sum(L, R) = S[R] - S[L - 1]

Now we can calculate the range sum with a time complexity of O(1). Below is a C++ solution that uses the cumulative sum array.

3. C++ Code Example

#include 
#include 
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector A(N);
    vector S(N + 1, 0); // S[0] is initialized to 0

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i]; // Calculate cumulative sum
    }

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        // Output the range sum
        cout << S[R] - S[L - 1] << endl;
    }
    return 0;
}

4. Code Explanation

Let’s explain the above code step by step:

  1. Input Gathering: We receive the size of the array N and the number of queries M, and we input the values of the array A.
  2. Cumulative Sum Array Creation: We calculate the cumulative sum for each index and store it in the S array. This array helps us easily find the sums of the values of the original array A.
  3. Query Processing: We input the starting and ending indices L and R for each query, and we calculate and output the sum of the range using the cumulative sum array S.

5. Performance Analysis

The time complexity of the above C++ code is O(N) for calculating the cumulative sum of the array A and O(1) for processing each query, making the overall time complexity O(N + M). This is a very efficient method, allowing for quick results even with thousands of queries.

6. Various Modified Problems

The range sum problem can have various modifications. For example:

  • Range Minimum/Maximum: It can be modified to find the minimum or maximum value for a given parameter.
  • Range Updates: In cases where a specific range of values needs to be changed and the range sum must be recalculated. In this case, segment trees can be utilized.
  • 2D Range Sum: A problem of calculating the sum of a specific range in a 2D array, where double cumulative sums can be used.

7. Conclusion

The range sum problem is one of the very useful techniques in programming and provides significant efficiency, especially when large-scale data processing is required. In this tutorial, we learned how to solve the range sum problem using a cumulative sum array. We can further enhance this technique through various modified problems. Practice solving various problems to build experience and achieve high scores on C++ coding tests.

As we conclude the tutorial, please leave any additional questions or requests in the comments.