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.
Problem Definition
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.
Example Problem
Let’s assume we have an array like the following.
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};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.
Approach to Solving the Problem
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?
Preprocessing Method
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.
Example of a Prefix Sum Array
Let’s look at how to create a prefix sum array.
int[] prefixSum = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++)
{
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
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].
Implementation
Now let’s implement the range sum algorithm using the prefix sum array in C#.
using System;
public class Program
{
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int[][] queries = { new int[] { 2, 5 }, new int[] { 0, 9 }, new int[] { 4, 7 } };
int[] result = RangeSum(arr, queries);
foreach (var sum in result)
{
Console.WriteLine(sum);
}
}
public static int[] RangeSum(int[] arr, int[][] queries)
{
int[] prefixSum = new int[arr.Length + 1];
for (int i = 0; i < arr.Length; i++)
{
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
int[] results = new int[queries.Length];
for (int i = 0; i < queries.Length; i++)
{
int l = queries[i][0];
int r = queries[i][1];
results[i] = prefixSum[r + 1] - prefixSum[l];
}
return results;
}
}
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.
Time Complexity Analysis
The time complexity of the algorithm described above is as follows.
- Creating the prefix sum array: O(N)
- Query processing: O(1) (accessing state information for each query)
As a result, this algorithm has a time complexity of O(N + Q), where Q is the number of queries. Thus, the range sum problem can be solved very efficiently through the prefix sum array.
Practical Exercise
Now test how well you understand the range sum problem. We encourage you to create and solve problems like the one below.
Problem: Finding the Maximum Value in a Specific Range
Try to solve the problem of finding the maximum value within a specific range of a given array. Use the prefix sum to solve this problem.
Conclusion
The range sum problem is a fundamental algorithm problem about calculating the sum within a range of an array. We learned how to use the prefix sum array to handle arrays efficiently. Such techniques can be usefully applied to more complex problems, so make sure to practice enough.
I hope this article helps you in your C# coding test preparation. Try solving more algorithm problems to improve your skills!