The interval sum problem, which is frequently asked in coding tests, is about efficiently calculating the sum of elements in a specific range within a given array. In this post, we will discuss the ‘Calculating Interval Sum 1’ problem.<\/p>\n
An integer N and M are given, along with an array consisting of N integers. Next, M queries are provided, each consisting of two integers S and E. The task is to calculate the sum from S to E. Note that S and E range from 1 to N.<\/p>\n
\n 5 3\n 1 2 3 4 5\n 1 3\n 2 4\n 3 5\n <\/pre>\nSample Output<\/h4>\n
\n 6\n 9\n 12\n <\/pre>\n4. Approach to the Problem<\/h2>\n
To calculate the interval sum, the simplest method can be used first. However, since the maximum values of N and M are 100,000, it is impossible with a time complexity of O(N * M). Therefore, we need to find an efficient way to calculate the interval sum.<\/p>\n
4.1. Simple Approach<\/h3>\n
The simplest method is to iterate from S to E to calculate the sum. However, this method has a complexity of O(N * M).<\/p>\n
4.2. Utilizing Cumulative Sum Array<\/h3>\n
One of the efficient approaches is to use a Cumulative Sum array. By creating the cumulative sum array first, we quickly calculate the answer for each query using the values of S and E.<\/p>\n
When defining the cumulative sum array, the i-th element of the array represents the sum from 1 to i. That is, the i-th value of the cumulative sum array is calculated as:<\/p>\n
\n sum[i] = sum[i - 1] + array[i - 1]\n <\/pre>\nWhen processing queries, the following formula can be used:<\/p>\n
\n result = sum[E] - sum[S - 1]\n <\/pre>\n5. Algorithm Implementation<\/h2>\n
Now let’s implement the algorithm using the cumulative sum array described above.<\/p>\n
5.1. Python Code<\/h3>\n
\ndef solve(N, M, array, queries):\n # Create cumulative sum array\n sum_array = [0] * (N + 1)\n \n # Calculate cumulative sum\n for i in range(1, N + 1):\n sum_array[i] = sum_array[i - 1] + array[i - 1]\n \n result = []\n \n # Process queries\n for S, E in queries:\n query_sum = sum_array[E] - sum_array[S - 1]\n result.append(query_sum)\n \n return result\n\n# Sample input\nN, M = 5, 3\narray = [1, 2, 3, 4, 5]\nqueries = [(1, 3), (2, 4), (3, 5)]\n\n# Output results\noutput = solve(N, M, array, queries)\nfor res in output:\n print(res)\n <\/pre>\n6. Code Explanation<\/h2>\n
The above code works in the following order:<\/p>\n
\n
- First, the cumulative sum array is initialized. The size of the cumulative sum array is set to N + 1 to easily calculate the sum from 1 to N.<\/li>\n
- Next, each element of the array is iterated to calculate the cumulative sum.<\/li>\n
- While going through the queries, the sum for the given S and E is quickly calculated using the cumulative sum array.<\/li>\n
- The calculated results are stored in a list to be output at the end.<\/li>\n<\/ol>\n
7. Time Complexity Analysis<\/h2>\n
The time complexity of the above algorithm is as follows:<\/p>\n
\n
- O(N) to create the cumulative sum array<\/li>\n
- O(M) to process M queries<\/li>\n<\/ul>\n
Thus, the overall time complexity is O(N + M), allowing us to solve the problem efficiently.<\/p>\n
8. Space Complexity Analysis<\/h2>\n
The space complexity is O(N) to store the cumulative sum array. Additional variables use constant space, so the overall space complexity is O(N).<\/p>\n
9. Conclusion<\/h2>\n
In this post, we discussed the interval sum problem. We learned how to solve the problem efficiently using a cumulative sum array and provided a Python code example to aid understanding. This method can be applied in various problems requiring interval sums and can serve as a basis to tackle more complex issues.<\/p>\n
10. Additional Exercises<\/h2>\n
Now, try to solve some exercises on your own. Below are a few additional practice problems.<\/p>\n