Day 137-Q5 | 3次元BIT（点加算・直方体和クエリ）

問題

$1\le x\le X$, $1\le y\le Y$, $1\le z\le Z$ を満たす整数格子点 $(x,y,z)$ 全体からなる3次元グリッドがあり、はじめすべての点に $0$ が書かれている。以下の2種類のクエリを $Q$ 個、順番に処理せよ。

0 x y z v : 点 $(x,y,z)$ に書かれている値へ $v$ を加算する。
1 x1 y1 z1 x2 y2 z2 : 直方体領域 $[x_1,x_2]\times[y_1,y_2]\times[z_1,z_2]$（両端を含む）の値の総和を出力する。

入力形式

X Y Z Q
query_1
...
query_Q

制約

$1 \le X,Y,Z \le 100$

$1 \le Q \le 2\times10^5$

$-10^4 \le v \le 10^4$

クエリ1は $x_1\le x_2, y_1\le y_2, z_1\le z_2$

入出力例

入力例1

3 3 3 5
0 1 1 1 5
0 2 2 2 3
0 3 1 2 -2
1 1 1 1 3 3 3
1 1 1 1 2 2 2

出力例1

6
8

概念図

ヒント（段階的開示）

ヒント1（方向性）

1次元BITは「点加算・区間和」を$O(\log N)$で処理できる。2次元BITは、1次元BITの各ノードに「もう1次元分のBIT」を入れ子にすることで矩形和クエリに拡張できる。この入れ子をもう1段重ねると、3次元でも同じように点加算・直方体和が処理できるはずである。

ヒント2（アプローチ）

3次元BITは「x方向にBITをたどりながら、各ノードでさらにy方向のBITをたどり、そのさらに各ノードでz方向のBITをたどる」3重の入れ子。加算は$O(\log X\log Y\log Z)$の3重ループ。直方体の和は、1次元の「区間和=累積和の差」を3次元に拡張した包除原理（$2^3=8$個の頂点それぞれの符号付き前方成分の和）で求める。

ヒント3（誘導）

def add(x, y, z, val):
    i = x
    while i <= X:
        j = y
        while j <= Y:
            k = z
            while k <= Z:
                tree[i][j][k] += val
                k += k & (-k)
            j += j & (-j)
        i += i & (-i)

def prefix(x, y, z):  # [1,x]x[1,y]x[1,z] の和
    s = 0
    i = x
    while i > 0:
        j = y
        while j > 0:
            k = z
            while k > 0:
                s += tree[i][j][k]
                k -= k & (-k)
            j -= j & (-j)
        i -= i & (-i)
    return s

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    X = int(data[idx]); idx += 1
    Y = int(data[idx]); idx += 1
    Z = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    tree = [[[0] * (Z + 1) for _ in range(Y + 1)] for _ in range(X + 1)]

    def add(x, y, z, val):
        i = x
        while i <= X:
            j = y
            while j <= Y:
                k = z
                while k <= Z:
                    tree[i][j][k] += val
                    k += k & (-k)
                j += j & (-j)
            i += i & (-i)

    def prefix(x, y, z):
        if x <= 0 or y <= 0 or z <= 0:
            return 0
        s = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                k = z
                while k > 0:
                    s += tree[i][j][k]
                    k -= k & (-k)
                j -= j & (-j)
            i -= i & (-i)
        return s

    def range_sum(x1, y1, z1, x2, y2, z2):
        total = 0
        for xi, xs in ((x2, 1), (x1 - 1, -1)):
            for yi, ys in ((y2, 1), (y1 - 1, -1)):
                for zi, zs in ((z2, 1), (z1 - 1, -1)):
                    total += xs * ys * zs * prefix(xi, yi, zi)
        return total

    out = []
    for _ in range(Q):
        t = int(data[idx]); idx += 1
        if t == 0:
            x = int(data[idx]); idx += 1
            y = int(data[idx]); idx += 1
            z = int(data[idx]); idx += 1
            v = int(data[idx]); idx += 1
            add(x, y, z, v)
        else:
            x1 = int(data[idx]); idx += 1
            y1 = int(data[idx]); idx += 1
            z1 = int(data[idx]); idx += 1
            x2 = int(data[idx]); idx += 1
            y2 = int(data[idx]); idx += 1
            z2 = int(data[idx]); idx += 1
            out.append(str(range_sum(x1, y1, z1, x2, y2, z2)))

    print("\n".join(out))


main()

Step-by-Step 解説

1BITの入れ子構造
1次元BITの各ノードtree[i]を「もう1次元分のBIT」に置き換え、それをさらに1段繰り返すことで3次元化する。3重ループを愚直にネストするだけでよい。

2加算のロジック
add(x,y,z,val)は「xに関するBITインデックスを進めながら、各段でyのインデックスを進め、その各段でzのインデックスを進めて+=val」という3重ループ。全体でO(log X log Y log Z)。

3前方和の3次元版
prefix(x,y,z)は「[1,x]×[1,y]×[1,z]」という原点を含む直方体の和。1次元の前方和を3重に入れ子にしただけ。

4包除原理による直方体和
1次元の区間和がprefix(r)-prefix(l-1)の2項の差で表せるのと同様、3次元の直方体和は2³=8個の頂点のprefixの符号付き和。各座標軸で「上限側(+1)」か「下限-1側(-1)」を独立に選び、3軸分の符号を掛け合わせる。

5prefixの境界処理
x1-1=0などグリッド端では自明に0。prefix関数の冒頭で座標が0以下なら即座に0を返すガードを入れる。

よくあるミス

ミス	原因	正しい書き方
直方体和の符号の組み合わせを間違える	2次元の4項パターンをそのまま拡張せず符号の掛け算を誤る	各軸で独立に(+1,上限)/(-1,下限-1)を選び、3軸分の符号の積にする
x1-1が0になるケースで誤った値になる	prefixにグリッド外の座標を渡すケースを考慮していない	prefixの先頭で座標が0以下なら0を返すガードを入れる
メモリ確保をXYZの大きさで愚直にやり過大になる	3次元配列サイズが座標範囲の積で効く	制約X,Y,Z≤100の範囲では101³≈10^6要素で収まることを確認する
ループの入れ子順序を間違える	変数名の使い回しでシャドーイングが起きる	i(x方向)・j(y方向)・k(z方向)を各階層で独立に管理する
クエリ読み込みのオフセット管理をズレさせる	クエリ種別で読み込む個数が異なることを考慮しない	クエリ0は4個、クエリ1は6個と分けてidxを進める

次のステップ

発展: 直方体加算・点参照（差分BITのトリックを3次元化）、あるいは直方体加算・直方体和（2次元BITの4本トリックを3次元へ一般化した8本のBIT構成、Day122-Q5の3次元版）に拡張せよ。
発展2: 座標範囲が$10^9$程度まで大きい場合、密な3次元配列は確保できない。座標圧縮や、動的セグメント木（Day120-Q1）の3次元版として辞書ベースの疎なBITに置き換える設計を検討せよ。

自己評価

完全理解おおむね理解要復習

Day 137-Q5 — 3次元BIT（点加算・直方体和クエリ）

問題