問題
$H\times W$ のグリッド（すべて0で初期化）に対し $Q$ 個のクエリを順に処理せよ。1 x1 y1 x2 y2 val: 矩形領域（1-indexed両端含む）の各マスに val を加算。2 x1 y1 x2 y2: 矩形領域の値の総和を出力。
入力形式
H W Q
query_1
...
query_Q制約
$1\le H,W\le1000$
$1\le Q\le2\times10^5$
$1\le x1\le x2\le H$
$1\le y1\le y2\le W$
$|\mathrm{val}|\le10^4$
累積値は $10^9$ 以内
入出力例
入力例1
3 3 4
1 1 1 2 2 5
1 2 2 3 3 3
2 1 1 3 3
2 2 2 2 2出力例1
32
8概念図: 矩形加算=4隅の点加算
ヒント（段階的開示）
ヒント1: 方向性
1次元では「区間[l,r]に一律valを足す・区間和を求める」を2本のBIT（差分配列BITと重み付き累積用BIT）で両方O(log N)にできる有名なテクニックがある。これを2次元に拡張すると何本のBITが要るか、次元が1つ増えるごとに情報量がどう増えるかを考えてみよう。
ヒント2: アプローチ
1次元の区間加算・区間和BITは差分配列d[i]=a[i]-a[i-1]を使い、累積和をΣd[i]とΣ(i-1)d[i]の2つのBITに帰着する。2次元では矩形加算を4隅の点加算に分解し、累積和の式変形をx方向・y方向それぞれに行うと、1,(x-1),(y-1),(x-1)(y-1)の4つの重みに対応する4本のBITが必要になる。
ヒント3: 誘導（コード骨格）
def prefix_sum(x, y):
return (x * y * query(b1, x, y)
- y * query(b2, x, y)
- x * query(b3, x, y)
+ query(b4, x, y))
def range_sum(x1, y1, x2, y2):
return (prefix_sum(x2, y2) - prefix_sum(x1-1, y2)
- prefix_sum(x2, y1-1) + prefix_sum(x1-1, y1-1))模範解答 (Python)
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
H = int(data[idx]); idx += 1
W = int(data[idx]); idx += 1
Q = int(data[idx]); idx += 1
b1 = [[0] * (W + 1) for _ in range(H + 1)]
b2 = [[0] * (W + 1) for _ in range(H + 1)]
b3 = [[0] * (W + 1) for _ in range(H + 1)]
b4 = [[0] * (W + 1) for _ in range(H + 1)]
def add(b, x, y, val):
i = x
while i <= H:
j = y
while j <= W:
b[i][j] += val
j += j & (-j)
i += i & (-i)
def point_add(x, y, val):
add(b1, x, y, val)
add(b2, x, y, val * (x - 1))
add(b3, x, y, val * (y - 1))
add(b4, x, y, val * (x - 1) * (y - 1))
def range_add(x1, y1, x2, y2, val):
point_add(x1, y1, val)
point_add(x2 + 1, y1, -val)
point_add(x1, y2 + 1, -val)
point_add(x2 + 1, y2 + 1, val)
def query_sum(b, x, y):
s = 0
i = x
while i > 0:
j = y
while j > 0:
s += b[i][j]
j -= j & (-j)
i -= i & (-i)
return s
def prefix_sum(x, y):
if x <= 0 or y <= 0:
return 0
return (x * y * query_sum(b1, x, y)
- y * query_sum(b2, x, y)
- x * query_sum(b3, x, y)
+ query_sum(b4, x, y))
def range_sum(x1, y1, x2, y2):
return (prefix_sum(x2, y2) - prefix_sum(x1 - 1, y2)
- prefix_sum(x2, y1 - 1) + prefix_sum(x1 - 1, y1 - 1))
out = []
for _ in range(Q):
t = int(data[idx]); idx += 1
if t == 1:
x1 = int(data[idx]); idx += 1
y1 = int(data[idx]); idx += 1
x2 = int(data[idx]); idx += 1
y2 = int(data[idx]); idx += 1
val = int(data[idx]); idx += 1
range_add(x1, y1, x2, y2, val)
else:
x1 = int(data[idx]); idx += 1
y1 = int(data[idx]); idx += 1
x2 = int(data[idx]); idx += 1
y2 = int(data[idx]); idx += 1
out.append(str(range_sum(x1, y1, x2, y2)))
print('\n'.join(out))
solve()計算量: 1クエリあたりO(log H log W)（定数倍4倍）。H,W≤8のランダムグリッドで200試行×最大30クエリを生成し、素朴な2次元配列シミュレーションと本実装を突き合わせて全一致を確認済み。
Step-by-Step 解説
11次元の復習
差分配列dを使い、Σa[x]=(X+1)Σd[i]−Σi·d[i]という式変形で2本のBITに帰着する。
差分配列dを使い、Σa[x]=(X+1)Σd[i]−Σi·d[i]という式変形で2本のBITに帰着する。
22次元への一般化
2階差分（4隅トリック）を取り、累積和を1,(x-1),(y-1),(x-1)(y-1)の4種類の重み付き総和で表現する。これがb1〜b4の4本のBITに対応する。
2階差分（4隅トリック）を取り、累積和を1,(x-1),(y-1),(x-1)(y-1)の4種類の重み付き総和で表現する。これがb1〜b4の4本のBITに対応する。
3矩形加算=4点のpoint_add
4隅(x1,y1)に+val、(x2+1,y1)と(x1,y2+1)に-val、(x2+1,y2+1)に+valを点加算する。
4隅(x1,y1)に+val、(x2+1,y1)と(x1,y2+1)に-val、(x2+1,y2+1)に+valを点加算する。
4累積和の合成とクエリの包除
prefix_sum(x,y)は4本のBITから式通りに合成する。任意の矩形和は1次元と同じ包除の2次元版（4つのprefix_sumの加減算）で求まる。
prefix_sum(x,y)は4本のBITから式通りに合成する。任意の矩形和は1次元と同じ包除の2次元版（4つのprefix_sumの加減算）で求まる。
5動作確認
200試行のランダムテストで素朴シミュレーションと全一致を確認済み。
200試行のランダムテストで素朴シミュレーションと全一致を確認済み。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 4隅の符号を間違える | 1次元の「lに+val、r+1に-val」を機械的に2次元へ拡張してしまう | 2次元では「対角の2点が+、他の2点が-」になる包除の形を正しく導出する |
| prefix_sumの式の係数を1次元のまま使う | x方向・y方向どちらの展開も必要なことを見落とす | 1,(x-1),(y-1),(x-1)(y-1)の4項すべてを正しい符号で組み合わせる |
| x1-1やy1-1が0になったときの処理漏れ | 座標0を1-indexedのBITにそのまま渡してしまう | prefix_sumの冒頭でx<=0 or y<=0なら0を返すガードを入れる |
| 矩形和クエリのたびにグリッド全体を走査する | BITの利点を使わず愚直にO(HW)で計算する | point_add/query_sumによる対数時間の演算に統一する |
次のステップ
- 発展: このトリックは加法の分配則に依存するため矩形最大値などには一般化できない。最大値系クエリには2次元セグメント木など別のデータ構造が必要になる点も押さえておくとよい。
- 次回予告: 次回のMaster Levelローテーションへ続く