Binary Indexed Trees in Scala

Scala で BIT を実装する

 

概要

• Binary Indexed Trees – topcoder

 

コード

 

実行例

REPL でコードを貼り付ける場合は :paste モードでの実行が必要。
(コンパニオンオブジェクトを同時に定義するため)

scala> :paste
// Entering paste mode (ctrl-D to finish)

...snip...

// Exiting paste mode, now interpreting.

defined class BinaryIndexedTree
defined object BinaryIndexedTree

scala> val b = BinaryIndexedTree[Int](6).updated(0 -> 1, 2 -> 2, 3 -> 1, 4 -> 1, 5 -> 3)
b: BinaryIndexedTree[Int] = BinaryIndexedTree(6,Vector(0, 1, 1, 2, 4, 1, 4))

scala> b.sum(6)              // 1 + 2 + 1 + 1 + 3
res0: Int = 8

scala> b.sum(2, 5)           // 2 + 1 + 1
res1: Int = 4

 

Related Posts

• mog project: Binary Indexed Tree (BIT) in C++