Python Coding Test Course, Finding Interval Sum 1

1. Problem Definition

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.

Problem Description

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.

2. Input and Output Format

Input

The first line contains N and M separated by a space. (1 ≤ N, M ≤ 100,000)
The second line contains N integers separated by spaces. (Each integer is between 1 and 100,000)
From the third line onward, M lines contain two queries. (S, E)

Output

Output the answer for each query over M lines.

3. Sample Input and Output

Sample Input

Sample Output

    6
    9
    12

4. Approach to the Problem

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.

4.1. Simple Approach

The simplest method is to iterate from S to E to calculate the sum. However, this method has a complexity of O(N * M).

4.2. Utilizing Cumulative Sum Array

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.

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:

    sum[i] = sum[i - 1] + array[i - 1]

When processing queries, the following formula can be used:

    result = sum[E] - sum[S - 1]

5. Algorithm Implementation

Now let’s implement the algorithm using the cumulative sum array described above.

5.1. Python Code

def solve(N, M, array, queries):
    # Create cumulative sum array
    sum_array = [0] * (N + 1)
    
    # Calculate cumulative sum
    for i in range(1, N + 1):
        sum_array[i] = sum_array[i - 1] + array[i - 1]
    
    result = []
    
    # Process queries
    for S, E in queries:
        query_sum = sum_array[E] - sum_array[S - 1]
        result.append(query_sum)
    
    return result

# Sample input
N, M = 5, 3
array = [1, 2, 3, 4, 5]
queries = [(1, 3), (2, 4), (3, 5)]

# Output results
output = solve(N, M, array, queries)
for res in output:
    print(res)

6. Code Explanation

The above code works in the following order:

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.
Next, each element of the array is iterated to calculate the cumulative sum.
While going through the queries, the sum for the given S and E is quickly calculated using the cumulative sum array.
The calculated results are stored in a list to be output at the end.

7. Time Complexity Analysis

The time complexity of the above algorithm is as follows:

O(N) to create the cumulative sum array
O(M) to process M queries

Thus, the overall time complexity is O(N + M), allowing us to solve the problem efficiently.

8. Space Complexity Analysis

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).

9. Conclusion

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.

10. Additional Exercises

Now, try to solve some exercises on your own. Below are a few additional practice problems.

Write a program to calculate the interval sum from 1 to 100.
Implement a program that calculates the sum of the interval each time an element changes.
Write a program to calculate the sum of a specific area in a two-dimensional array.

11. Questions and Feedback

If you have any questions or feedback regarding the content discussed in this article, feel free to leave a comment. Let’s solve problems together!