C# Coding Test Course, Calculating Interval Sum 3

Many people preparing for coding tests need systematic learning for algorithm problem solving. Today, we will discuss the problem of calculating the range sum. In particular, the ‘Range Sum Query 3’ problem is an interesting problem that can utilize various strategies. In this article, I will explain the definition of the problem, the solution method, implementation in C# code, and time complexity analysis in detail.

Problem Definition

Given an integer array arr and multiple queries query, each query represents the start and end of a range. Our goal is to efficiently calculate and return the range sum for each query.

Example

Array: arr = [1, 2, 3, 4, 5]
Query: query = [[1, 3], [0, 2], [2, 4]]
Output: [9, 6, 12]

In the above example, the first query means the range from index 1 to 3, so 2 + 3 + 4 = 9. The remaining queries can be handled in the same way.

Approach to the Problem

There are several ways to solve the problem, but when the number of elements in the array is large, performance can be an important factor. Therefore, an efficient algorithm is essential.

1. Traditional Method

The most basic approach is to directly sum the values of the array for each query. However, this method has the following drawbacks:

  • The time complexity is O(n), making it inefficient when the number of queries increases.
  • It is very inefficient when the number of elements in the array is large.

2. Using Prefix Sum

To solve the problem more efficiently, the exposed method is to use Prefix Sum. The prefix sum array is defined as follows:

sum[i] = arr[0] + arr[1] + ... + arr[i]

Using this calculated prefix sum array, we can quickly compute the given range sum. The sum of the range [left, right] is obtained as sum[right] - sum[left - 1]. This way, the time complexity can be reduced to O(1).

3. C# Code Implementation

Now, let’s implement the code to calculate the prefix sum using the C# language based on the given problem.


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Define array and queries
        int[] arr = { 1, 2, 3, 4, 5 };
        int[][] queries = { new int[] { 1, 3 }, new int[] { 0, 2 }, new int[] { 2, 4 } };

        // List to store the range sums
        List results = new List();

        // Create prefix sum array
        int[] prefixSum = new int[arr.Length];
        prefixSum[0] = arr[0];

        for (int i = 1; i < arr.Length; i++)
        {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        // Calculate range sum for each query
        foreach (var query in queries)
        {
            int left = query[0];
            int right = query[1];

            if (left == 0)
            {
                results.Add(prefixSum[right]);
            }
            else
            {
                results.Add(prefixSum[right] - prefixSum[left - 1]);
            }
        }

        // Output results
        Console.WriteLine(string.Join(", ", results));
    }
}

Code Analysis and Explanation

The above code is designed to convert the array into a prefix sum in advance so that the range sum for each query can be calculated in O(1) time. The following steps are taken:

  1. Create Prefix Sum Array: After initializing the first element of the array, a loop is used to calculate the prefix sum for each element.
  2. Execute Queries: Iterate through each query to calculate the range sum. If the left boundary is 0, the prefix sum can be retrieved directly; otherwise, the range sum is obtained by finding the difference of two elements.
  3. Output Results: Each result is printed.

Time Complexity Analysis

The time complexity of this algorithm is as follows:

  • Time to create the prefix sum array: O(n)
  • Time to calculate the range sum for each query: O(1) (proportional to the number of queries)

Thus, the overall time complexity can be represented as O(n + m), where m is the number of queries. This is an efficient method when dealing with many queries.

Conclusion

Today, we explored how to design and implement an efficient algorithm through the "Range Sum Query 3" problem. Algorithm problems may be simple concepts, but finding solutions through various approaches is a very important skill for coding tests. I hope this course helps you in writing your own code and solving problems.

Through the utilization of code and improvement of algorithms, I hope to elevate your coding test skills to the next level. See you in the next course!