object IntervalTree1 extends App{    val score = Array(1, 2, 3, 4, 5)    val commands = Array(        "Q 1 5", "U 3 6", "Q 3 4",        "Q 4 5", "U 2 9", "Q 1 5"    )    val (n, m) = (5, 6)    val iTree = new IntervalTree    var root: Tree = _    root = iTree.build(1, n)    //iTree.printTree(root)    commands.foreach( cmd => {        val tokens = cmd.split(" ")        val (c, a, b) = (tokens(0), tokens(1).toInt, tokens(2).toInt)        c match {            case "Q" => println(iTree.query(root, a, b))            case "U" => {score(a) = b; iTree.update(root, a, b)}        }    })    class Tree    {        var l: Tree = null        var r: Tree = null        var lv = 0        var rv = 0        var maxscore = 0    }    class IntervalTree    {        var pos = 0        var nodes = Array.fill(400010)(new Tree())        def build(left: Int, right: Int): Tree =        {            val node = nodes(pos); pos += 1            node.lv = left; node.rv = right;            if (left == right) {                node.maxscore = Math.max(score(left - 1), score(right - 1))                node            }            else {                val mid = (left + right) >> 1                node.l = build(left, mid)                node.r = build(mid + 1, right)                node.maxscore = Math.max(node.l.maxscore, node.r.maxscore)            }            node        }        def query(root: Tree, left: Int, right: Int): Int =        {            if (left == root.lv && right == root.rv) return root.maxscore            val mid = (root.lv + root.rv) >> 1            mid match {                case m if (right <= m) => query(root.l, left, right)                case m if (left > m) => query(root.r, left, right)                case _ => Math.max(query(root.l, left, mid), query(root.r, mid + 1, right))            }        }        def update(root: Tree, value: Int, newValue: Int): Int =        {            val mid = (root.lv + root.rv) >> 1            if (value =http://www.mamicode.com/= root.lv &&  value == root.rv) {"[${node.lv},${node.rv}]")                printTree(node.l)                printTree(node.r)            }        }    }}