C++ Coding Test Course, Finding Interval Sums 3

Approach to the Problem

The range sum problem can be solved in various ways, but an efficient approach is to use
Prefix Sum. With prefix sums, you can calculate the sum for the given range
[left, right] in O(1) time complexity.

The basic idea is to precompute and store the sum for each index in the array.
With this, the sum of a specific range can be calculated as follows.

sum(left, right) = prefixSum[right] - prefixSum[left - 1]

Here, prefixSum[i] is the sum from the start of the array to the i-th element.
This method has a time complexity of O(N) since it involves one traversal of the array, and afterwards, each range sum can be computed in O(1).

Implementation

Code

#include <iostream>
#include <vector>

using namespace std;

class SubarraySum {
public:
    SubarraySum(const vector<int>& arr) {
        int n = arr.size();
        prefixSum.resize(n + 1);
        prefixSum[0] = 0; // prefixSum[0] is initialized to 0.
        
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }
    }

    int getSum(int left, int right) {
        return prefixSum[right] - prefixSum[left - 1];
    }

private:
    vector<int> prefixSum; // Array to store the prefix sum.
};

int main() {
    int n; // Size of the array
    cout << "Enter the size of the array: ";
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    SubarraySum subarray(arr);

    int left, right;
    cout << "Enter the left boundary of the range (starting from 1): ";
    cin >> left;
    cout << "Enter the right boundary of the range: ";
    cin >> right;

    int result = subarray.getSum(left, right);
    cout << "The sum of the range [" << left << ", " << right << "] is: " << result << endl;

    return 0;
}
    

Code Explanation

Class Definition

The SubarraySum class provides the functionality to calculate range sums.
The constructor of this class initializes the prefix sum based on the array elements provided.
It defines a variable n to store the size of the array and creates the prefixSum array (including one for [0]).

Prefix Sum Calculation

Through the for loop inside the constructor, the array is traversed to store
the sums up to each index in the prefixSum array.
This is unique because it has a size of one more than the array size, starting from the first index.

Range Sum Calculation

The getSum(int left, int right) method returns the range sum using the provided left and right indices. It easily calculates the range sum using
prefixSum[right] - prefixSum[left - 1].

Testing and Usage

With this code, users can input the left and right boundaries of the range and easily calculate
the sum of that range. This algorithm runs smoothly even as the input array size increases,
allowing for the range sum to be processed quickly in O(1) time complexity.

Conclusion

The range sum problem is widely used in various applications, and
this prefix sum approach demonstrates its utility in areas like data analysis and statistical processing.
This simple yet effective method can enhance the efficiency of problem-solving.

I hope this lecture aids you in preparing for your C++ coding tests!