Problem Description
Given an integer array A and several pairs of integers L and R, write a program to find the sum of the interval from index L to index R for each pair.
For example, if A = [1, 2, 3, 4, 5] and the interval pairs are (1, 3), (0, 2), (2, 4),
the results should be 9, 6, and 12 respectively.
Input Format
- The first line contains an integer N (1 ≤ N ≤ 100,000): size of array A
- The second line contains N integers A[i] (1 ≤ A[i] ≤ 10,000).
- The third line contains an integer M (1 ≤ M ≤ 100,000): number of interval pairs.
- The following M lines contain the interval pairs L, R (0 ≤ L <= R < N).
Output Format
- Output the sum of each interval over M lines.
Problem Solving Strategy
While it is possible to solve this problem using simple loops,
the worst-case scenario has N and M up to 100,000, making O(N * M) time complexity impossible.
Therefore, a method with O(N + M) time complexity is needed.
To achieve this, it is useful to create a prefix sum array as a preprocessing step.
Using a prefix sum array allows for quick calculation of each interval’s sum.
Prefix Sum Array Description
First, calculate the prefix sum of array A to create the prefix_sum array.
prefix_sum[i] stores the sum from A[0] to A[i].
Thus, the sum from index L to index R can be calculated as follows:
sum(L, R) = prefix_sum[R] – prefix_sum[L – 1], L > 0
sum(0, R) = prefix_sum[R], L = 0
Code Implementation
def compute_prefix_sum(A):
prefix_sum = [0] * len(A)
prefix_sum[0] = A[0]
for i in range(1, len(A)):
prefix_sum[i] = prefix_sum[i - 1] + A[i]
return prefix_sum
def range_sum(prefix_sum, L, R):
if L == 0:
return prefix_sum[R]
else:
return prefix_sum[R] - prefix_sum[L - 1]
def main():
N = int(input())
A = list(map(int, input().split()))
M = int(input())
prefix_sum = compute_prefix_sum(A)
results = []
for _ in range(M):
L, R = map(int, input().split())
results.append(range_sum(prefix_sum, L, R))
for result in results:
print(result)
if __name__ == "__main__":
main()
Code Explanation
1. The compute_prefix_sum function calculates the prefix sum of the input array A and
returns the prefix_sum array. It initializes the first value and calculates each index’s value by adding the previous value to the current value.
2. The range_sum function quickly calculates the sum of the interval using the prefix sum array
for the given L and R. If L is 0, it returns prefix_sum[R]; otherwise, it calculates the result by subtracting
prefix_sum[L-1] from prefix_sum[R].
3. The main function handles input and calls the range_sum function for each interval pair to display the results.
Time Complexity Analysis
– It takes O(N) time to calculate the prefix sum array.
– Each of the M queries takes O(1) time.
Thus, the overall time complexity is O(N + M).
Conclusion
In this lecture, we covered an efficient approach to finding interval sums.
Utilizing prefix sums allows for reduced time complexity, enabling quick processing even for large inputs.
This technique is useful in various algorithm problems, so it’s important to keep it in mind.
Additional Practice Problems
- 1. Change the example array A and compute the interval sums.
- 2. Research methods to calculate interval sums using other algorithms (Segment Tree or Fenwick Tree).
- 3. Practice problems involving updating the value at a specific index in the array and recalculating the total interval sums.
References
– Competitive Programming Problem Sets
– Materials related to online coding tests
– Interval sum problems from LeetCode and HackerRank