{"id":34138,"date":"2024-11-01T09:24:39","date_gmt":"2024-11-01T09:24:39","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34138"},"modified":"2024-11-01T10:58:27","modified_gmt":"2024-11-01T10:58:27","slug":"c-coding-test-course-range-sum","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34138\/","title":{"rendered":"C++ Coding Test Course, Range Sum"},"content":{"rendered":"

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.<\/p>\n

1. Problem Description<\/h2>\n

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

For example, suppose the array A<\/code> is as follows:<\/p>\n

\nA = [10, 20, 30, 40, 50]\n<\/pre>\n
And let’s assume the following queries are given:<\/p>\n
\n1. L = 1, R = 3\n2. L = 0, R = 4\n3. L = 2, R = 2\n<\/pre>\n
Calculating the range sum for the given queries yields the following results:<\/p>\n
\n1. A[1] + A[2] + A[3] = 20 + 30 + 40 = 90\n2. A[0] + A[1] + A[2] + A[3] + A[4] = 10 + 20 + 30 + 40 + 50 = 150\n3. A[2] = 30\n<\/pre>\n
2. Problem Solving Approach<\/h2>\n
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<\/code> queries spends O(R - L + 1)<\/code> time, in the worst case, it will take O(N * M)<\/code> time. To improve this, we can use the following method.<\/p>\n
2.1. Preprocessing Method – Cumulative Sum Array<\/h3>\n
To quickly calculate the sum of all queries, we can utilize a cumulative sum array. First, we define the cumulative sum array S<\/code> for the given array A<\/code>. The cumulative sum array is calculated as follows:<\/p>\n
\nS[i] = S[i - 1] + A[i]\n<\/pre>\n
Here, S[0]<\/code> is initialized to 0. Using the cumulative sum array, the sum of a range can be calculated easily as follows:<\/p>\n
\nsum(L, R) = S[R] - S[L - 1]\n<\/pre>\n
Now we can calculate the range sum with a time complexity of O(1)<\/code>. Below is a C++ solution that uses the cumulative sum array.<\/p>\n
3. C++ Code Example<\/h2>\n
\n#include \n#include \nusing namespace std;\n\nint main() {\n    int N, M;\n    cin >> N >> M;\n\n    vector A(N);\n    vector S(N + 1, 0); \/\/ S[0] is initialized to 0\n\n    for (int i = 0; i < N; i++) {\n        cin >> A[i];\n        S[i + 1] = S[i] + A[i]; \/\/ Calculate cumulative sum\n    }\n\n    for (int i = 0; i < M; i++) {\n        int L, R;\n        cin >> L >> R;\n        \/\/ Output the range sum\n        cout << S[R] - S[L - 1] << endl;\n    }\n    return 0;\n}\n<\/long><\/int><\/vector><\/iostream><\/pre>\n
4. Code Explanation<\/h2>\n
Let\u2019s explain the above code step by step:<\/p>\n
    \n
  1. Input Gathering:<\/strong> We receive the size of the array N<\/code> and the number of queries M<\/code>, and we input the values of the array A<\/code>.<\/li>\n
  2. Cumulative Sum Array Creation:<\/strong> We calculate the cumulative sum for each index and store it in the S<\/code> array. This array helps us easily find the sums of the values of the original array A<\/code>.<\/li>\n
  3. Query Processing:<\/strong> We input the starting and ending indices L<\/code> and R<\/code> for each query, and we calculate and output the sum of the range using the cumulative sum array S<\/code>.<\/li>\n<\/ol>\n
    5. Performance Analysis<\/h2>\n
    The time complexity of the above C++ code is O(N)<\/code> for calculating the cumulative sum of the array A<\/code> and O(1)<\/code> for processing each query, making the overall time complexity O(N + M)<\/code>. This is a very efficient method, allowing for quick results even with thousands of queries.<\/p>\n
    6. Various Modified Problems<\/h2>\n
    The range sum problem can have various modifications. For example:<\/p>\n