RubyでBIT Binary Indexed Treeを作ってみた

BIT (Binary Indexed Tree)を使うと

• 累積和が簡単に求められる
• 転倒数が簡単に求められる

アルゴリズム関係では良く出てくる技っぽいです。
BITの詳しい説明や転倒数については、他のサイトにすごくわかりやすく書かれているのでそちらを参照してください。

Rubyで書くとこんな感じ。

# Binary Indexed Tree
class BIT

  @bit = []
  @N = 0

  def initialize(size)
    @N = size
    @bit = Array.new(@N + 1, 0)
  end

  # 追加, a: index (1オリジン), w: 追加する値
  def add(a, w)
    x = a + 1
    while (x <= @N)
      @bit[x] += w
      x += (x & -x)
    end
  end

  # a番目までの累積和 (1オリジン)
  def sum(a)
    ret = 0
    x = a
    while (x > 0)
      ret += @bit[x]
      x -= (x & -x)
    end

    ret
  end

  def print()
    "BIT: #{@bit}"
  end

end

list = [1,3,5,7,9,13]
b = BIT.new(list.size)
(0...list.size).each do |x|
  b.add(x, list[x])
end

pp "Sum => #{b.sum(1)}"
pp "Sum => #{b.sum(2)}"

BITは1オリジン(インデックスが1から始まる)のでそこは注意が必要です。