ARC #075 E より
Index が微妙にずれる気がする…
class BIT attr_reader :bit def initialize(n) @n = n @bit = Array.new(@n + 1, 0) end def sum(i) s = 0 while i > 0 s += @bit[i] i -= i & -i end return s end def add(i, x) i += 1 while i <= @n @bit[i] += x i += i & -i end end end