kotlin coding test course, interval sum

1. Introduction

Hello. In this session, we will learn about how to efficiently calculate the interval sum in Kotlin.
This is one of the problems frequently encountered in coding tests, where we need to find the sum over a specific interval of a given sequence.
Through this process, we will discuss various methods to solve the interval sum problem and their respective time complexities.

2. Problem Description

Given a sequence A and a query Q, each query is given by two integers L and R.
We need to quickly find the sum from L to R.

Input

The first line contains the size of the sequence N and the number of queries M.
The second line consists of N integers forming the sequence A.
For the next M lines, L and R are given.

Output

Print the result for each query one line at a time.

Constraints

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

3. Approach

There are several ways to calculate the interval sum, but the basic approaches are as follows.

3.1. Simple Iteration

The most intuitive method is to directly calculate the sum in the defined range for each query. However, this method has a time complexity of O(N), and in the worst case, it becomes O(N * M) = O(10^10) when the maximum number of queries is 100,000, making it very inefficient.

3.2. Cumulative Sum Array

By using the following methodology, we can efficiently calculate the interval sum.

A cumulative sum array is an array that pre-calculates the sum up to a specific position, which can be created in linear time O(N).
This allows each query to be processed in O(1). Thus, the overall time complexity is O(N + M).

4. Implementation

Let’s implement the interval sum calculation algorithm using the cumulative sum array in Kotlin.


fun main() {
    val reader = System.`in`.bufferedReader()
    val (n, m) = reader.readLine().split(" ").map { it.toInt() }

    val array = reader.readLine().split(" ").map { it.toInt() }.toIntArray()
    val sumArray = IntArray(n + 1)

    // Create cumulative sum array
    for (i in 1..n) {
        sumArray[i] = sumArray[i - 1] + array[i - 1]
    }

    val result = StringBuilder()
    // Process queries
    repeat(m) {
        val (l, r) = reader.readLine().split(" ").map { it.toInt() }
        val sum = sumArray[r] - sumArray[l - 1]
        result.append(sum).append("\n")
    }

    println(result)
}

The key point in the above implementation is that we can process each query in O(1) through sumArray.
The sum of the interval [L, R] can be easily calculated as sumArray[R] - sumArray[L-1].

5. Time Complexity Analysis

Analyzing the time complexity of this algorithm, we have:

Creating the cumulative sum array: O(N)
Processing queries: O(M)
Total time complexity: O(N + M)

Therefore, under the given constraints, we can efficiently calculate the interval sum.

6. Example

6.1. Input Example

6.2. Output Example


6
14
15

In the above example, the results of the queries given as input are that the sum from 1 to 3 is 6,
the sum from 2 to 5 is 14, and the total sum from 1 to 5 is 15.

7. Conclusion

In this lecture, we explored various ways to calculate the interval sum and its precise implementation.
In particular, we discussed in depth about how to efficiently compute the interval sum using the cumulative sum array.
This algorithm can be effectively used in many coding test problems and practical applications. In the next session, we will explore more complex data structures and algorithms.