🦆
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から始まる)のでそこは注意が必要です。
Discussion