Swift Coding Test Course, Finding the Sum of Intervals 3

In this lecture, we will learn how to solve the range sum problem using Swift.

Problem Description

Let’s consider the following problem.

An array A consisting of N integers and M queries are given. Each query is provided as two integers i and j, and we need to calculate the sum from A[i] to A[j].

The size of the array N and the number of queries M are as follows:

• 1 ≤ N, M ≤ 100,000
• -10,000 ≤ A[i] ≤ 10,000
• 1 ≤ i ≤ j ≤ N

Input Example

The input format is as follows:

        5 3
        1 2 3 4 5
        1 3
        2 4
        1 5
    

In the above input, the first line represents the size of the array N and the number of queries M. The second line contains the elements of the array A. The subsequent M lines represent each query.

Output Example

The sum for each of the queries from the input should be output.

        6
        9
        15
    

Problem Solving Method

A efficient way to solve this problem is to use prefix sums. That is, by calculating the prefix sums of array A in advance, we can determine the sum of each query in constant time.

Step 1: Calculate Prefix Sums

Create a prefix sum array prefixSum such that prefixSum[i] stores the sum of the first element of array A up to the i-th element.

    let N = 5
    let A = [1, 2, 3, 4, 5]
    var prefixSum = [Int](repeating: 0, count: N + 1)

    for i in 1...N {
        prefixSum[i] = prefixSum[i - 1] + A[i - 1]
    }
    

Step 2: Process Queries

When processing the queries, use prefixSum[j] - prefixSum[i - 1] to obtain the sum from i to j. This allows the time complexity for each query to be O(1).

    let queries = [(1, 3), (2, 4), (1, 5)]
    for query in queries {
        let i = query.0
        let j = query.1
        let result = prefixSum[j] - prefixSum[i - 1]
        print(result)
    }
    

Complete Code

Combining the above explanations, the complete code is as follows.

    let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
    let N = firstLine[0] // Size of the array
    let M = firstLine[1] // Number of queries

    let A = readLine()!.split(separator: " ").map { Int($0)! }
    var prefixSum = [Int](repeating: 0, count: N + 1)

    for i in 1...N {
        prefixSum[i] = prefixSum[i - 1] + A[i - 1]
    }

    for _ in 0..
Time Complexity
The time complexity of this algorithm is O(N + M). Here, N is the size of array A, and M is the number of queries. This is due to the O(N) for summing all elements of A and O(M) for processing M queries combined.
Conclusion
In this lecture, we learned how to use prefix sums to solve the range sum problem. This method can significantly improve performance. I encourage you to apply this technique when solving similar problems in the future.



	
관련