セグメント木によるRMQの実装

SegTree.kt

class SegTree(val _n: Int){
    val n: Int
    val d: IntArray
    init{
        var i = 1
        while(i < _n) i *= 2
        n = i
        d = IntArray(2 * n - 1){Int.MAX_VALUE}
    }
    fun update(k: Int, x: Int){
        var k = k + n - 1
        d[k] = x
        while(k > 0){
            k = (k - 1) / 2
            d[k] = minOf(d[k * 2 + 1], d[k * 2 + 2])
        }
    }
    fun query(a: Int, b: Int, k: Int, l: Int = 0, r: Int = n): Int{
        if(r <= a || b <= l) return Int.MAX_VALUE
        if(a <= l && r <= b) return d[k]
        return minOf(
            query(a, b, k * 2 + 1, l, (l + r) / 2),
            query(a, b, k * 2 + 2, (l + r) / 2, r)
        )
    }
    fun dump(){
        var i = 0
        while(1.shl(i) <= n){
            println(d.drop(1.shl(i)-1).take(1.shl(i)).joinToString())
            i++
        }
    }
}
fun main(){
    val N = readInt()
    val A = readInts()
    val Q = readInt()
    val st = SegTree(N)
    for((i, a) in A.withIndex()){
        st.update(i, a)
    }
    st.dump()
    repeat(Q){
        val q = readInts()
        if(q[0] == 1){
            val(_, l, r) = q
            println(st.query(l, r, 0))
        } else {
            val(_, k, x) = q
            st.update(k, x)
        }
    }
}
/*
8
5 3 7 9 6 4 1 2
7
1 0 5
2 0 2
1 0 5
2 0 -1
1 0 3
1 4 7
1 0 7

*/

val br = System.`in`.bufferedReader()
fun readLine() = br.readLine()!!
fun readInt() = readLine().toInt()
fun readInts() = readLine().split(" ").map(String::toInt)
fun readLong() = readLine().toLong()
fun readLongs() = readLine().split(" ").map(String::toLong)
fun <T>printAll(a: Iterable<T>) = println(a.joinToString("\n"))