プログラミングコンテストチャレンジブック(3-4)
Binary Indexed Treeって面白いデータ構造だ。
プログラミングコンテストチャレンジブックこのデータ構造を使ってバブルソートの交換回数を数えるんだけど、理屈がいまいちわからん。BITの示しているのが交換しなくていい組の数なのはわかるんだけど、なぜ左から順繰りにアペンドしていくのかがしっくりこない。
class Bit(object): def __init__(self,l): self.size = l self.bit = [0] * (self.size+1) def sum(self, i): s = 0 while i > 0: s += self.bit[i] i -= i & -i return s def add(self, i, x): while i <= self.size: self.bit[i] += x i += i & -i def __str__(self): return str(self.bit) if __name__ == '__main__': a = [3,1,4,2] ans = 0 bit = Bit(len(a)) for i,v in enumerate(a): ans += i - bit.sum(v) bit.add(v,1) print "%d: ans=%d v=%d %s" % (i, ans, v, bit) print ans
実行するとこんな感じ
0: ans=0 v=3 [0, 0, 0, 1, 1] 1: ans=1 v=1 [0, 1, 1, 1, 2] 2: ans=1 v=4 [0, 1, 1, 1, 3] 3: ans=3 v=2 [0, 1, 2, 1, 4] 3
わかりやすい説明ないかなぁ。