RMQ tree

rmq.kt

package rmq

import java.util.ArrayList
import java.io.InputStreamReader
import java.io.BufferedReader
import java.util.StringTokenizer

trait RMQTree {
    fun getMinimum(from: Int, to: Int): Int
}
class SingletonRMQTree(val value: Int): RMQTree {
    override fun getMinimum(from: Int, to: Int): Int {
        return value
    }
}
class BranchRMQTree(val midPoint: Int, val left: RMQTree, val right: RMQTree): RMQTree {
    override fun getMinimum(from: Int, to: Int): Int {
        var result = Integer.MAX_VALUE
        if (from < midPoint) {
            result = Math.min(result, left.getMinimum(from, Math.min(midPoint, to)))
        }
        if (midPoint < to) {
            result = Math.min(result, right.getMinimum(Math.max(midPoint, from), to))
        }
        return result
    }
}

data class AugmentedTree(val tree: RMQTree, val from: Int, val to: Int) { }

fun iter(from: Int, to: Int, increment: Int, closure: (Int) -> Unit) {
    var i = from
    while (i < to) {
        closure(i)
        i += increment
    }
}

class Scanner(val reader: BufferedReader) {
    private var st: StringTokenizer? = null
    fun nextInt(): Int {
        while (st == null || !st!!.hasMoreTokens()) {
            st = StringTokenizer(reader.readLine())
        }
        return Integer.parseInt(st!!.nextToken())
    }
}

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val sc = Scanner(reader)
    val size = sc.nextInt()
    val data = IntArray(size)

    var current = ArrayList<AugmentedTree>()
    for (i in data.indices) {
        val number = sc.nextInt()
        val tree = SingletonRMQTree(number)
        current.add(AugmentedTree(tree, i, i + 1))
    }

    while (current.size() > 1) {
        val next = ArrayList<AugmentedTree>()
        iter(0, current.size(), 2) { i ->
            if (i + 1 < current.size()) {
                val left = current[i].tree
                val right = current[i + 1].tree
                val midPoint = current[i].to

                next.add(AugmentedTree(BranchRMQTree(midPoint, left, right), current[i].from, current[i + 1].to))
            } else {
                next.add(current[i])
            }
        }

        current = next
    }

    val tree = current[0].tree

    val queries = sc.nextInt()
    for (_ in 1..queries) {
        val from = sc.nextInt() - 1
        val to = sc.nextInt()

        println(tree.getMinimum(from, to))
    }
}