kotlin coding test course, segment tree

A Segment Tree is a data structure that efficiently computes range sums, minimums, maximums, and more. This data structure performs particularly well in situations where interval queries and updates occur frequently. In this tutorial, we will cover the basic structure and implementation of the Segment Tree, as well as problems that can be utilized in practical coding tests.

What is a Segment Tree?

A Segment Tree is a binary tree data structure used to store information about specific intervals of an array. Each node stores information for a specific interval, allowing for fast queries and updates. It is mainly used to perform the following two operations efficiently:

Range Query: Calculation of sum, minimum, maximum, etc. for a specific range
Update: Changing the value at a specific position

Structure of the Segment Tree

A Segment Tree is made up of a complete binary tree and is typically structured in the following way. For this, each node of the Segment Tree is defined through the relationship between parent and child. The rules for the array nodes are as follows:

The left child of a parent node at index i is 2*i, and the right child is 2*i + 1
Leaf nodes are stored at the corresponding indices of the given array.

Implementation of the Segment Tree

Let’s take a look at the implementation of a Segment Tree using Kotlin. First, we will define a basic Segment Tree class and implement initialization, update, and query functionalities.

1. Define the Segment Tree Class


class SegmentTree(private val array: IntArray) {
    private val size: Int = array.size
    private val tree: IntArray = IntArray(4 * size)
    
    init {
        build(0, 0, size - 1)
    }

    private fun build(node: Int, start: Int, end: Int) {
        if (start == end) {
            tree[node] = array[start]
        } else {
            val mid = (start + end) / 2
            build(2 * node + 1, start, mid)
            build(2 * node + 2, mid + 1, end)
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
        }
    }

    fun update(index: Int, value: Int) {
        update(0, 0, size - 1, index, value)
    }

    private fun update(node: Int, start: Int, end: Int, index: Int, value: Int) {
        if (start == end) {
            array[index] = value
            tree[node] = value
        } else {
            val mid = (start + end) / 2
            if (index in start..mid) {
                update(2 * node + 1, start, mid, index, value)
            } else {
                update(2 * node + 2, mid + 1, end, index, value)
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
        }
    }
    
    fun query(L: Int, R: Int): Int {
        return query(0, 0, size - 1, L, R)
    }

    private fun query(node: Int, start: Int, end: Int, L: Int, R: Int): Int {
        if (R < start || end < L) return 0 // Query range does not overlap with node range
        if (L <= start && end <= R) return tree[node] // Node range is within query range
        val mid = (start + end) / 2
        val leftSum = query(2 * node + 1, start, mid, L, R)
        val rightSum = query(2 * node + 2, mid + 1, end, L, R)
        return leftSum + rightSum
    }
}

2. Example Usage

Let's take a look at an example of using the Segment Tree defined above to calculate range sums and perform updates.


fun main() {
    val array = intArrayOf(1, 3, 5, 7, 9, 11)
    val segmentTree = SegmentTree(array)

    println("Sum of range [1, 3]: ${segmentTree.query(1, 3)}") // 3 + 5 + 7 = 15
    segmentTree.update(1, 10) // Update array[1] to 10
    println("Sum of range [1, 3] after update: ${segmentTree.query(1, 3)}") // 10 + 5 + 7 = 22
}

Coding Test Problem

Now, let's solve a problem that frequently appears in coding tests. The following problem is an application problem using the Segment Tree.

Problem: Range Sum and Update

This problem requires calculating the sum for a specific range of a given array, with the additional functionality to update the value at a specific index.

Problem Description

- A given array consisting of N integers.
- Based on previous query results, perform the following operations Q times.
    1. The query "1 L R" requests the sum from the array indices L to R.
    2. The query "2 X Y" updates the value at index X to Y.

Input Format

- The first line will contain the size of the array N and the number of queries Q.
- The second line will contain N integers.
- The following Q lines will contain the queries.

Output Format

- For each "1 L R" query, output the sum of the range.

Example Input

Example Output

Problem Solution

To solve this problem, we will implement a Segment Tree to efficiently execute range sum queries and update operations. The structure receives data from input, initializes the Segment Tree, and processes the queries.

Implementation


fun main() {
    val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    val array = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val segmentTree = SegmentTree(array)

    repeat(q) {
        val query = readLine()!!.split(" ").map { it.toInt() }
        if (query[0] == 1) {
            // Range sum query
            val sum = segmentTree.query(query[1] - 1, query[2] - 1)
            println(sum)
        } else if (query[0] == 2) {
            // Update query
            segmentTree.update(query[1] - 1, query[2])
        }
    }
}

Conclusion

In this course, we learned the fundamental concepts and implementation methods of the Segment Tree. The Segment Tree is a very useful data structure for efficient range queries and updates, and it appears frequently in coding test problems. I hope this example has helped you understand the applications of the Segment Tree, and that it will assist you in solving various problems in the future.

When preparing for coding tests, it is important to systematically learn various data structures and algorithms to enhance your application skills. I encourage you to continue developing better problem-solving abilities through a variety of data structures and algorithms.