Ad-hoc polymorphic Fenwick Tree https://medium.com/@dr0ff/ad-hoc-polymorphic-fenwick-tree-8a10264b8443#.2iz5c1nkx

Fenwick.scala

package com.github.drewnoff.algorithm

import scala.reflect.ClassTag
import scala.math.max


trait Associative[A] {
  def id: A
  def op(a: A, b: A): A
}


object Associative {
  implicit val associativeIntSum = new Associative[Int] {
    override def id = 0
    override def op(a: Int, b: Int) = a + b
  }
}


case class Fenwick[A : Associative : ClassTag] private (values: Array[A]) {
  def this(sz: Int) = this(Array.fill(sz)(implicitly[Associative[A]].id))

  val ev: Associative[A] = implicitly[Associative[A]]

  def update(ix: Int, value: A): Fenwick[A] = {
    def loop(vs: Array[A], ix: Int): Fenwick[A] =
      if (ix < values.size)
        loop(vs.updated(ix, ev.op(vs(ix), value)),
          ix + ((ix + 1) & -(ix + 1)))
      else
        new Fenwick(vs)

    loop(values, ix)
  }

  // Returns the result from applying operation to elements from index 0 to i
  def query(ix: Int): A = {
    def loop(res: A, ix: Int): A =
      if (ix < 0)
        res
      else
        loop(ev.op(res, values(ix)), ix - ((ix + 1) & -(ix + 1)))
    loop(ev.id, ix)
  }
}


object Fenwick {

  // Usage example
  def main(args: Array[String]): Unit = {
    println("===sum===")
    val addSeq = List((0, 3), (1, 2), (2, 5), (2, 5))
    val fenwick = addSeq.foldLeft(new Fenwick(3))((fw, op) => fw.update(op._1, op._2))

    println(fenwick.query(0) == 3)
    println(fenwick.query(1) == 5)
    println(fenwick.query(2) == 15)

    println("===max===")
    implicit val associativeIntMax = new Associative[Int] {
      override def id = Int.MinValue
      override def op(a: Int, b: Int) = max(a, b)
    }

    val upSeq = List((0, 3), (1, 2), (2, 5))
    val maxFenwick = upSeq.foldLeft(new Fenwick(3))((fw, op) => fw.update(op._1, op._2))
    println(maxFenwick.query(0) == 3)
    println(maxFenwick.query(1) == 3)
    println(maxFenwick.query(2) == 5)
    println((maxFenwick.update(2, -1)).query(2) == 5) // Fenwick max tree allows only increase values in Array
  }
}