python BinaryIndexedTree

自分のライブラリ置き場です。
データ構造 BinaryIndexedTree ( 別名 FenwickTree )( 略称 BIT ) の python コードです。

正直汎用性は低いです。
こんなことができます。

• a[i] += x add(i, x)
• a[l, r) の総和 sum(l, r)

[l, r) は (l, l+1, l+2, ... , r-2, r-1) みたいな区間のことです。半開区間っていいます。
半開区間は [l, m) と [m, r) を合わせると [l, r) になる、のような理由などがあるので便利です。

# BinaryIndexedTree
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    return self.sum_sub(j) - self.sum_sub(i)

使用例です。本体は最上部とかに貼り付けるだけなので省略しています。
長さ N の数列 a = {0, 0, ... , 0} 、Q 個のクエリ
t=0 なら a[x] += y
t=1 なら a[x, y) の総和を求める

n, q = map(int, input().split())
bit = BinaryIndexedTree(n)
for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 0:
    bit.add(x, y)
  if t == 1:
    print(bit.sum(x, y))

長さ N の数列 a = {0, 0, ... , 0} 、Q 個のクエリ
t=0 なら a[x] = y
t=1 なら a[x, y) の総和を求める

n, q = map(int, input().split())
bit = BinaryIndexedTree(n)
a = [0]*n
for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 0:
    bit.add(x, y-a[x])
    a[x] = y
  if t == 1:
    print(bit.sum(x, y))

長さ N の数列 a が与えられる、Q 個のクエリ
t=0 なら a[x] += y
t=1 なら a[x, y) の総和を求める

n, q = map(int, input().split())
a = list(map(int, input().split()))
bit = BinaryIndexedTree(n)
for i in range(n):
  bit.add(i, a[i])
for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 0:
    bit.add(x, y)
  if t == 1:
    print(bit.sum(x, y))

演算を少し変更できます。アーベル群なら BIT で使えるのですが、私は足し算とかけ算と xor しか知りません。
かけ算も、逆元を求めるのに時間がかかってしまうのでセグ木のほうがいいと思います。

長さ N の数列 a = {0, 0, ... , 0} 、Q 個のクエリ
t=0 なら a[x] ^= y
t=1 なら a[x, y) の xor を求める

class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] ^= x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    while i:
      a ^= self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    return self.sum_sub(j) ^ self.sum_sub(i)

n, q = map(int, input().split())
bit = BinaryIndexedTree(n)
for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 0:
    bit.add(x, y)
  if t == 1:
    print(bit.sum(x, y))

長さ N の数列 a = {1, 1, ... , 1} 、Q 個のクエリ
t=0 なら a[x] *= y ( y は 1 以上の整数 )
t=1 なら a[x, y) の総乗を求める ( 素数 mod )

class BinaryIndexedTree:
  def __init__(self, n, mod):
    self.bit = [1] * n
    self.mod = mod
  
  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] = self.bit[i-1]*x % mod
      i += i & -i

  def sum_sub(self, i):
    a = 1
    while i:
      a = a*self.bit[i-1] % mod
      i -= i & -i
    return a

  def sum(self, i, j):
    return self.sum_sub(j)*pow(self.sum_sub(i), mod-2, mod) % mod

mod = 10**9+7
n, q = map(int, input().split())
bit = BinaryIndexedTree(n, mod)
for _ in range(q):
  t, x, y = map(int, input().split())
  if t == 0:
    bit.add(x, y)
  if t == 1:
    print(bit.sum(x, y))