Author: root

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.

	

Introduction

In today’s lecture, we will delve deep into the problem of calculating range sums. This problem frequently appears in various algorithmic challenges, and it’s essential to know efficient solutions.
In this article, we will define the problem, explain various approaches, and detail the process of finding the optimal solution.

Problem Definition

Given an array A and two integers L and R, calculate the value of
A[L] + A[L+1] + ... + A[R].
Assume that the index of A starts from 1.

Input

• First line: Integer N (1 ≤ N ≤ 100,000) – Size of the array
• Second line: N integers A[1], A[2], ..., A[N] (-1,000,000 ≤ A[i] ≤ 1,000,000)
• Third line: Integer Q (1 ≤ Q ≤ 100,000) – Number of queries
• Next Q lines: Each query contains two integers L and R

Output

For each query, output the range sum result line by line.

Problem Approach

There are several methods to solve this problem. A straightforward approach is to compute the sum directly for each query, but
this can be inefficient in terms of time complexity. Therefore, we will consider the following approach.

1. Approach through Simple Iteration

The most basic method is to use a loop to calculate the range sum for each query directly.
The time complexity of this method is O(N), and if there are Q queries, it becomes O(N*Q).
This would require up to a billion calculations in the worst-case scenario when both N and Q are at their maximum of 100,000, which is impractical.

2. Using a Cumulative Sum Array

Thus, using a cumulative sum array to solve the problem is much more efficient. With this approach,
the range sum can be resolved in O(1) time complexity. By creating a cumulative sum array and preprocessing the data linearly,
we can obtain results in O(1) time for each query.

Definition of Cumulative Sum Array

We will define the array p as follows:
p[i] = A[1] + A[2] + ... + A[i]
This way, the range sum A[L] + A[L+1] + ... + A[R] can be easily calculated as
p[R] - p[L-1].

Implementation

Now, let’s proceed with the actual implementation. I will write the algorithm using Swift.

    import Foundation

    // Input
    let n = Int(readLine()!)!
    let a = readLine()!.split(separator: " ").map { Int($0)! }
    let q = Int(readLine()!)!

    // Initialize cumulative sum array
    var p = [0] + a
    
    // Create cumulative sum array
    for i in 1..