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.
Problem Description
Given an array as follows, write a program to efficiently calculate the sum of specific ranges for multiple query pairs.
Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Query: [(1, 3), (2, 5), (3, 7)]When 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.
Approach to the Problem
There are various basic approaches to solve the range sum problem. I will start with the simplest method and explain more efficient ones.
1. Using Simple Iteration
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.
def simple_range_sum(arr, queries):
results = []
for start, end in queries:
results.append(sum(arr[start - 1:end])) # 1-based index to 0-based index
return results
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
queries = [(1, 3), (2, 5), (3, 7)]
print(simple_range_sum(arr, queries)) # Output: [9, 14, 27]When 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.
2. Using a Cumulative Sum Array
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.
def prefix_sum(arr):
n = len(arr)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + arr[i - 1]
return prefix
def efficient_range_sum(arr, queries):
prefix = prefix_sum(arr)
results = []
for start, end in queries:
results.append(prefix[end] - prefix[start - 1]) # 1-based index adjustment
return results
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
queries = [(1, 3), (2, 5), (3, 7)]
print(efficient_range_sum(arr, queries)) # Output: [9, 14, 27]In 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.
Problem Optimization and Selection
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.
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.
Conclusion
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!