金魚亭日常

読書,ガジェット,競技プログラミング

Binary Indexed Tree

ARC #075 E より

arc075.contest.atcoder.jp

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

AtCoder ARC #075 / ABC #063