{"id":33960,"date":"2024-11-01T09:22:26","date_gmt":"2024-11-01T09:22:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33960"},"modified":"2024-11-01T10:54:43","modified_gmt":"2024-11-01T10:54:43","slug":"c-coding-test-course-interval-sum","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33960\/","title":{"rendered":"C# Coding Test Course, Interval Sum"},"content":{"rendered":"
\n

Hello, everyone! Today we will discuss one of the important topics in coding tests using C#, which is ‘Range Sum’. The range sum problem is about efficiently calculating the sum of a specific range in an array. This problem is a very useful topic that frequently appears in many algorithm problems and practical work.<\/p>\n

Problem Definition<\/h2>\n

Before we start the problem, let me briefly explain what a range sum is. A range sum means calculating the sum of a specific range of a given array (e.g., from array[i] to array[j]). Such problems can be presented in various ways.<\/p>\n

Example Problem<\/h3>\n

Let’s assume we have an array like the following.<\/p>\n

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};<\/code><\/pre>\n
Now we will solve a problem that requests the range sum of the given array. For example, if i and j are 2 and 5 respectively, we must calculate the sum from arr[2] to arr[5], which is 3 + 4 + 5 + 6 = 18.<\/p>\n
Approach to Solving the Problem<\/h2>\n
The first method to calculate the range sum is to use a simple loop. We can traverse the elements of the array to calculate the sum of the range corresponding to the values of i and j. However, this has the disadvantage of being inefficient with a time complexity of O(N). So how can we calculate the range sum more efficiently?<\/p>\n
Preprocessing Method<\/h3>\n
To efficiently solve the range sum problem, we use the concept of a ‘prefix sum array’. A prefix sum array is an array that stores the sum up to each index, allowing us to easily calculate the range sum. Using a prefix sum array allows us to calculate the range sum in O(1) time complexity.<\/p>\n
Example of a Prefix Sum Array<\/h4>\n
Let’s look at how to create a prefix sum array.<\/p>\n
\n    int[] prefixSum = new int[arr.Length + 1];\n    for (int i = 0; i < arr.Length; i++)\n    {\n        prefixSum[i + 1] = prefixSum[i] + arr[i];\n    }\n    <\/code><\/pre>\n
In the above code, we store the sum of the arr array up to the i-th index in the i+1-th index of the prefixSum array. Now the sum of a specific range [i, j] can be easily calculated as prefixSum[j + 1] – prefixSum[i].<\/p>\n
Implementation<\/h2>\n
Now let’s implement the range sum algorithm using the prefix sum array in C#.<\/p>\n
\n    using System;\n\n    public class Program\n    {\n        public static void Main()\n        {\n            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };\n            int[][] queries = { new int[] { 2, 5 }, new int[] { 0, 9 }, new int[] { 4, 7 } };\n\n            int[] result = RangeSum(arr, queries);\n            foreach (var sum in result)\n            {\n                Console.WriteLine(sum);\n            }\n        }\n\n        public static int[] RangeSum(int[] arr, int[][] queries)\n        {\n            int[] prefixSum = new int[arr.Length + 1];\n            for (int i = 0; i < arr.Length; i++)\n            {\n                prefixSum[i + 1] = prefixSum[i] + arr[i];\n            }\n\n            int[] results = new int[queries.Length];\n            for (int i = 0; i < queries.Length; i++)\n            {\n                int l = queries[i][0];\n                int r = queries[i][1];\n                results[i] = prefixSum[r + 1] - prefixSum[l];\n            }\n\n            return results;\n        }\n    }\n    <\/code><\/pre>\n
When the above code is executed, the range sums for each query can be calculated. It is important to ensure that the index ranges are always valid.<\/p>\n
Time Complexity Analysis<\/h2>\n
The time complexity of the algorithm described above is as follows.<\/p>\n