Hello, everyone! Today we will tackle the range sum problem, which frequently appears in coding tests using Python. The range sum problem asks how to quickly calculate the sum of a specific range, and it’s an important concept that forms the basis of many algorithmic problems. We will explore various approaches to solve this problem.<\/p>\n
Given an array as follows, write a program to efficiently calculate the sum of specific ranges for multiple query pairs.<\/p>\n
Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\nQuery: [(1, 3), (2, 5), (3, 7)]<\/code><\/pre>\nWhen the above array and queries are provided, the queries are given in the form of (start index, end index). For example, the query (1, 3) means that we need to calculate the sum from index 1 to index 3 of the array (1-based index). In this case, it should be 2 + 3 + 4 = 9.<\/p>\n
Approach to the Problem<\/h2>\n
There are various basic approaches to solve the range sum problem. I will start with the simplest method and explain more efficient ones.<\/p>\n
1. Using Simple Iteration<\/h3>\n
The most intuitive method is to calculate the sum for the required range directly. This method is good when there are few queries, but it is inefficient when there are many. We can implement it as follows.<\/p>\n
def simple_range_sum(arr, queries):\n results = []\n for start, end in queries:\n results.append(sum(arr[start - 1:end])) # 1-based index to 0-based index\n return results\n\n\narr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\nqueries = [(1, 3), (2, 5), (3, 7)]\nprint(simple_range_sum(arr, queries)) # Output: [9, 14, 27]<\/code><\/pre>\nWhen we execute the code above, the results for the queries will output [9, 14, 27]. However, the time complexity of this method is O(Q * N), where Q is the number of queries and N is the size of the array. This becomes inefficient for large inputs.<\/p>\n
2. Using a Cumulative Sum Array<\/h3>\n
A more efficient way is to create a cumulative sum array. Once we have the cumulative sum array, we can calculate the sum of each range in O(1) time. The method is as follows.<\/p>\n
def prefix_sum(arr):\n n = len(arr)\n prefix = [0] * (n + 1)\n for i in range(1, n + 1):\n prefix[i] = prefix[i - 1] + arr[i - 1]\n return prefix\n\n\ndef efficient_range_sum(arr, queries):\n prefix = prefix_sum(arr)\n results = []\n for start, end in queries:\n results.append(prefix[end] - prefix[start - 1]) # 1-based index adjustment\n return results\n\n\narr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\nqueries = [(1, 3), (2, 5), (3, 7)]\nprint(efficient_range_sum(arr, queries)) # Output: [9, 14, 27]<\/code><\/pre>\nIn the above code, calculating the cumulative sum array takes O(N) time, and processing each query takes O(1) time. Thus, the overall time complexity reduces to O(N + Q). This method allows us to handle multiple queries efficiently.<\/p>\n
Problem Optimization and Selection<\/h2>\n
The range sum problem can be utilized in various situations, and the algorithm chosen may vary depending on the conditions of the problem. It is essential to choose the optimal method considering the size of the input array, the number of queries, and the length of each query’s range.<\/p>\n
Besides the methods described above, more complex data structures such as segment trees can also be used, but this tutorial focused on basic methods for solving practical problems. In the next lesson, we will address more complicated dynamic query problems.<\/p>\n
Conclusion<\/h2>\n
In this lesson, we covered the range sum problem using Python. We found that while simple iteration can be inefficient, using a cumulative sum array allows us to solve the problem much more efficiently. The range sum problem is a very useful topic for building basic algorithm skills, so I encourage you to practice it multiple times and try various variations!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"