Python Coding Test Course, Finding Interval Sums 2

Hello! Welcome to the Python coding test course. In this course, we will
cover the “Interval Sum Problem 2”. Efficiently calculating the interval sum
is very important in solving algorithm problems.
Below, we will look at the problem description and solution process step by step.

Problem Description

Given N integers A[1], A[2], …, A[N],
Q queries are provided. Each query consists of two integers L and R,
and the goal is to find the sum from A[L] to A[R].
The problem is as follows:

Input Format:
The first line contains the integers N (1 ≤ N ≤ 100,000) and Q (1 ≤ Q ≤ 100,000).
The second line contains N integers separated by spaces. |A[i]| ≤ 1,000,000
The Q queries are given as follows: each query consists of two integers L and R (1 ≤ L ≤ R ≤ N).

Output Format:
Print the sum from A[L] to A[R] for each query.

How to Solve the Problem Efficiently

To solve such problems, it is efficient to use the prefix sum
instead of calculating the sum for each query.
The prefix sum allows you to calculate the sum of a specific interval in constant time O(1).

Calculating Prefix Sum

The method to calculate the prefix sum is as follows:

• Create a prefix sum array S, where S[i] represents the sum from A[1] to A[i].
• Initialize S[0] = 0. (For convenience, 0 is added so that the calculation can be done by subtracting S[L-1] from S[i].)
• Then calculate S[i] as follows: S[i] = S[i-1] + A[i]

This allows us to find the interval sum with a single subtraction operation as S[R] – S[L-1].

Solution Code

        
def calculate_prefix_sum(arr):
    n = len(arr)
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
    return prefix_sum

def range_sum(prefix_sum, L, R):
    return prefix_sum[R] - prefix_sum[L - 1]

N, Q = map(int, input().split())
A = list(map(int, input().split()))
prefix_sum = calculate_prefix_sum(A)

for _ in range(Q):
    L, R = map(int, input().split())
    print(range_sum(prefix_sum, L, R))
        
        

The above code performs the following steps:

• First, it calls a function to calculate the prefix sum array for the given array A of length N.
• For each query, it receives L and R, and outputs the sum for that interval.

Time Complexity Analysis

Analyzing the time complexity of this problem yields the following:

• It takes O(N) time to calculate the prefix sum array.
• It takes O(1) time to calculate the interval sum for each query.
• Thus, the overall time complexity is O(N + Q).

Conclusion

The interval sum problem is one of the frequently asked questions in coding tests.
Using prefix sums is a good method to solve the problem efficiently.
Based on what we have covered in this course, it would also be good to try solving various variations of the problem.
If you have any additional questions or want to know more about other algorithm problems, feel free to leave a comment!