SegTree.scala

sealed trait SegTree {
  def size: Int
  def v: Int
  def query(a: Int, b: Int): Int
  def update(a: Int, k: Int): SegTree
}

case class Leaf(v: Int) extends SegTree {
  override val size = 1
  override def query(a: Int, b: Int): Int = v
  override def update(a: Int, k: Int): SegTree = Leaf(a)
}

case class Node(v: Int, left: SegTree, right: SegTree) extends SegTree {
  override val size = left.size + right.size
  override def query(a: Int, b: Int): Int = {
    val ls = left.size
    if (b <= 0 || size <= a) Int.MaxValue
    else math.min(left.query(a, b), right.query(a-ls, b-ls))
  }
  override def update(a: Int, k: Int): SegTree =
    if (k < left.size) {
      val newL = left.update(a, k)
      Node(math.min(newL.v, right.v), newL, right)
    }
    else {
      val newR = right.update(a, k-left.size)
      Node(math.min(left.v, newR.v), left, newR)
    }
}

object SegTree {
  def mkTree(nn: Int): SegTree = nn match {
    case 1 => Leaf(Int.MaxValue)
    case _ => {
      val n = Stream.iterate(1)(2.*).takeWhile(nn.>=).last
      Node(Int.MaxValue, mkTree(n/2), mkTree(n/2))
    }
  }
}