2 次元 BIT
$H \times W$ のマス目の値について、加算と和の取得をそれぞれ $O(\log H \log W)$ で行います。添字はすべて 0-indexed で、長方形は $\mathrm{x1} \le x < \mathrm{x2}$ かつ $\mathrm{y1} \le y < \mathrm{y2}$ の半開区間で指定します。使う方のクラスだけを貼れば動きます。メモリは $O(HW)$ です。
BIT2D(1 点加算・長方形の和):
BIT2D(h, w, a): $H \times W$ の初期配列a(省略するとすべて $0$)から構築。 $O(HW)$add(x, y, v):a[x][y]に $v$ を足すsum(x1, y1, x2, y2): 長方形の中の値の和prefix(x, y): $[0, x) \times [0, y)$ の値の和get(x, y):a[x][y]set(x, y, v):a[x][y]を $v$ にする
RangeBIT2D(長方形加算・長方形の和):
RangeBIT2D(h, w): すべて $0$ で構築add(x1, y1, x2, y2, v): 長方形の中のすべての値に $v$ を足すsum(x1, y1, x2, y2),prefix(x, y),get(x, y):BIT2Dと同じ
DualBIT2D(長方形加算・1 点取得):
DualBIT2D(h, w): すべて $0$ で構築add(x1, y1, x2, y2, v): 長方形の中のすべての値に $v$ を足すget(x, y):a[x][y]
DualBIT2D は 2 次元の差分を BIT で持ち、 $(x, y)$ までの累積和を値とします。RangeBIT2D でも同じことができますが、BIT が 1 つなので速くて軽いです。
RangeBIT2D は、2 次元の差分 $d$ に対して、 $[0, X) \times [0, Y)$ の和が $\sum d_{x,y} (X - x + 1)(Y - y + 1)$( $x, y$ は 1-indexed)と書けることを使い、 $d,\ d \cdot y,\ d \cdot x,\ d \cdot xy$ の 4 つを BIT で持ちます。
例:
b = BIT2D(3, 4)
b.add(1, 2, 5)
print(b.sum(0, 0, 2, 3)) # 5
r = RangeBIT2D(3, 4)
r.add(0, 0, 2, 2, 1)
print(r.sum(0, 0, 3, 4)) # 4
q = DualBIT2D(3, 4)
q.add(1, 1, 3, 3, 2)
print(q.get(2, 2)) # 2
コード
class BIT2D:
# 一点加算・長方形の和
def __init__(self, h, w, a=None):
# a: h×w の初期配列(省略時は全て0)。O(HW)で構築
self.h = h
self.w = w
W = w + 1
d = [0] * ((h + 1) * W)
if a is not None:
for i in range(h):
row = a[i]
base = (i + 1) * W
for j in range(w):
d[base + j + 1] = row[j]
for i in range(1, h + 1):
base = i * W
for j in range(1, w + 1):
k = j + (j & -j)
if k <= w:
d[base + k] += d[base + j]
for i in range(1, h + 1):
k = i + (i & -i)
if k <= h:
bi = i * W
bk = k * W
for j in range(1, w + 1):
d[bk + j] += d[bi + j]
self.d = d
def add(self, x, y, v):
# a[x][y] += v
d = self.d
h, w = self.h, self.w
W = w + 1
i = x + 1
while i <= h:
base = i * W
j = y + 1
while j <= w:
d[base + j] += v
j += j & -j
i += i & -i
def prefix(self, x, y):
# [0, x) × [0, y) の和
d = self.d
W = self.w + 1
s = 0
i = x
while i > 0:
base = i * W
j = y
while j > 0:
s += d[base + j]
j -= j & -j
i -= i & -i
return s
def sum(self, x1, y1, x2, y2):
# [x1, x2) × [y1, y2) の和
return (self.prefix(x2, y2) - self.prefix(x1, y2)
- self.prefix(x2, y1) + self.prefix(x1, y1))
def get(self, x, y):
return self.sum(x, y, x + 1, y + 1)
def set(self, x, y, v):
self.add(x, y, v - self.get(x, y))
class RangeBIT2D:
# 長方形加算・長方形の和
def __init__(self, h, w):
self.h = h
self.w = w
n = (h + 1) * (w + 1)
self.b0 = [0] * n
self.b1 = [0] * n
self.b2 = [0] * n
self.b3 = [0] * n
def _add(self, x, y, v):
# 1-indexedの差分点 (x, y) に v を加算
h, w = self.h, self.w
W = w + 1
b0, b1, b2, b3 = self.b0, self.b1, self.b2, self.b3
vy = v * y
vx = v * x
vxy = vx * y
i = x
while i <= h:
base = i * W
j = y
while j <= w:
k = base + j
b0[k] += v
b1[k] += vy
b2[k] += vx
b3[k] += vxy
j += j & -j
i += i & -i
def add(self, x1, y1, x2, y2, v):
# [x1, x2) × [y1, y2) の全要素に v を加算
self._add(x1 + 1, y1 + 1, v)
self._add(x1 + 1, y2 + 1, -v)
self._add(x2 + 1, y1 + 1, -v)
self._add(x2 + 1, y2 + 1, v)
def prefix(self, x, y):
# [0, x) × [0, y) の和
W = self.w + 1
b0, b1, b2, b3 = self.b0, self.b1, self.b2, self.b3
q0 = q1 = q2 = q3 = 0
i = x
while i > 0:
base = i * W
j = y
while j > 0:
k = base + j
q0 += b0[k]
q1 += b1[k]
q2 += b2[k]
q3 += b3[k]
j -= j & -j
i -= i & -i
return (x + 1) * (y + 1) * q0 - (x + 1) * q1 - (y + 1) * q2 + q3
def sum(self, x1, y1, x2, y2):
# [x1, x2) × [y1, y2) の和
return (self.prefix(x2, y2) - self.prefix(x1, y2)
- self.prefix(x2, y1) + self.prefix(x1, y1))
def get(self, x, y):
return self.sum(x, y, x + 1, y + 1)
class DualBIT2D:
# 長方形加算・一点取得
def __init__(self, h, w):
self.h = h
self.w = w
self.d = [0] * ((h + 1) * (w + 1))
def _add(self, x, y, v):
# 1-indexedの差分点 (x, y) に v を加算
d = self.d
h, w = self.h, self.w
W = w + 1
i = x
while i <= h:
base = i * W
j = y
while j <= w:
d[base + j] += v
j += j & -j
i += i & -i
def add(self, x1, y1, x2, y2, v):
# [x1, x2) × [y1, y2) の全要素に v を加算
self._add(x1 + 1, y1 + 1, v)
self._add(x1 + 1, y2 + 1, -v)
self._add(x2 + 1, y1 + 1, -v)
self._add(x2 + 1, y2 + 1, v)
def get(self, x, y):
# a[x][y]
d = self.d
W = self.w + 1
s = 0
i = x + 1
while i > 0:
base = i * W
j = y + 1
while j > 0:
s += d[base + j]
j -= j & -j
i -= i & -i
return s