Hello! Today, we will address one of the frequently asked problems in coding tests using C#, which is the “Calculate Interval Sum” problem. Through this problem, we aim to enhance our understanding of arrays and interval sums, and learn algorithms to solve this efficiently.<\/p>\n<\/div>\n
The interval sum problem can be defined as follows:<\/p>\n
Given an integer array The input consists of the size of the array The above input is as follows:<\/p>\n The output is the interval sum for each query:<\/p>\n Now, let’s go through the steps to solve this problem. We will start with a simple<\/strong> approach and then progress to a more efficient<\/strong> method.<\/p>\n The most intuitive method is to directly calculate the sum according to the starting and ending indices of each query. However, this method can be inefficient. For example, in the worst case, if the size of the array is This code calculates the sum for each query based on the input array elements provided by the user. However, this method is inefficient for large datasets.<\/p>\n An efficient way is to use a cumulative sum array<\/strong>. The cumulative sum pre-calculates the sum up to each index in the array, reducing the processing time for queries.<\/p>\n That is, <\/p>\n To calculate the interval sum:<\/p>\n This reduces the query processing time to This code first computes the cumulative sum array and then efficiently calculates the interval sum for each query using the starting and ending indices.<\/p>\n<\/div>\narr<\/code> and several queries (starting index and ending index), write a program to calculate the sum of the respective interval for each query.<\/p>\nn<\/code>, the elements of the array, the number of queries q<\/code>, and the starting index l<\/code> and ending index r<\/code> for each query.<\/p>\n<\/div>\nInput Example<\/h2>\n
\n 5\n 1 2 3 4 5\n 3\n 1 3\n 2 4\n 1 5\n <\/pre>\n
\n
5<\/code><\/li>\n[1, 2, 3, 4, 5]<\/code><\/li>\n3<\/code><\/li>\nOutput Example<\/h2>\n
\n 6\n 9\n 15\n <\/pre>\n
\n
1 + 2 + 3 = 6<\/code><\/li>\n2 + 3 + 4 = 9<\/code><\/li>\n1 + 2 + 3 + 4 + 5 = 15<\/code><\/li>\n<\/ul>\n<\/div>\nSolving the Problem<\/h2>\n
1. Simple Approach<\/h3>\n
n<\/code> and the number of queries is q<\/code>, the time complexity can reach O(n * q)<\/code>.<\/p>\nC#\n using System;\n\n class Program\n {\n static void Main()\n {\n int n = int.Parse(Console.ReadLine());\n int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n int q = int.Parse(Console.ReadLine());\n\n for (int i = 0; i < q; i++)\n {\n var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n int l = query[0] - 1; \/\/ 0-based index\n int r = query[1] - 1; \/\/ 0-based index\n\n int sum = 0;\n for (int j = l; j <= r; j++)\n {\n sum += arr[j];\n }\n Console.WriteLine(sum);\n }\n }\n }\n <\/code><\/pre>\n2. Efficient Approach: Cumulative Sum Array<\/h3>\n
C#\n sum[i] = arr[0] + arr[1] + ... + arr[i]\n <\/code><\/pre>\nC#\n interval_sum = sum[r] - sum[l-1]\n <\/code><\/pre>\nO(1)<\/code>. The overall time complexity becomes O(n + q)<\/code>.<\/p>\nC#\n using System;\n\n class Program\n {\n static void Main()\n {\n int n = int.Parse(Console.ReadLine());\n int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n int q = int.Parse(Console.ReadLine());\n \n long[] sum = new long[n + 1];\n \n for (int i = 1; i <= n; i++)\n {\n sum[i] = sum[i - 1] + arr[i - 1];\n }\n\n for (int i = 0; i < q; i++)\n {\n var query = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n int l = query[0] - 1; \/\/ 0-based index\n int r = query[1] - 1; \/\/ 0-based index\n\n long result = sum[r + 1] - sum[l];\n Console.WriteLine(result);\n }\n }\n }\n <\/code><\/pre>\n