baseerhk

object RandomAccessList {
  type RandomAccessList[A] = List[(CompleteBinaryTree[A], Int)]

  def fromList[A](xs: List[A]): RandomAccessList[A] = {
    def sublists[A](xs: List[A]): List[(List[A], Int)] = {
      def inner(xs: List[A], size: Int, acc: List[(List[A], Int)]): List[(List[A], Int)] = size match {
        case 0 => acc
        case s => {
          val s_ = Math.pow(2, Math.floor(Math.log(s + 1) / Math.log(2))).toInt - 1
          inner(xs.take(s - s_), s - s_, (xs.drop(s - s_), s_)::acc)

baseerhk

sealed trait CompleteBinaryTree[A] {
  def lookup(size: Int, index: Int): A = (this, index) match {
    case (Leaf(x), 0)                        => x
    case (Leaf(_), _)                        => throw new Exception("Index is not in list.")
    case (Node(x, _, _), 0)                  => x
    case (Node(x, l, _), i) if i <= size / 2 => l.lookup(size / 2, i - 1)
    case (Node(x, _, r), i) if i > size / 2  => r.lookup(size / 2, i - 1 - size / 2)
  }
  def update(size: Int, index: Int, y: A): CompleteBinaryTree[A] = (this, index) match {
    case (Leaf(_), 0)                        => Leaf(y)