はじめに
次のような問題を考えましょう。
問題 (Rectangle Add Rectangle Sum)
整数 $x, y$ に対して、$2$ 次元平面上の矩形領域 $[x, x + 1) \times [y, y + 1)$ をマス $(x,y)$ とよぶ。初め、全てのマスの重みは $0$ である。整数 $x, y$ に対して、マス $(x,y)$ の重みを $w _ {x, y}$ と表すことにする。
以下のいずれかの形式で表されるクエリが合計で $Q$ 個与えられるので、順番に処理せよ。
- $\mathrm{add}(v,l,r,d,u)$ : 矩形領域 $[l, r) \times [d, u)$ に含まれる全てのマスの重みに $v$ を加算する。即ち、$l \leq x \lt r$ かつ $d \leq y \lt u$ を満たす全ての整数 $x, y$ について、$w _ {x, y} \leftarrow w _ {x, y} + v$ と更新する。
- $\mathrm{sum}(l,r,d,u)$ : 矩形領域 $[l, r) \times [d, u)$ に含まれる全てのマスの重みの総和を計算する。即ち、$\displaystyle \sum _ {x = l} ^ {r - 1} \sum _ {y = d} ^ {u - 1} w _ {x, y}$ を計算する。
本記事では、$\mathrm{sum}$ クエリより後に $\mathrm{add}$ クエリが来ない場合の問題 (Static Rectangle Add Rectangle Sum) と、そのような制約が無い一般の問題 (Rectangle Add Rectangle Sum) を扱います。
クエリ先読みが可能という仮定の下で、Static Rectangle Add Rectangle Sum を $\Theta(Q)$ space, $\Theta(Q \log Q)$ time で解くアルゴリズムおよび Rectangle Add Rectangle Sum を $\Theta(Q \log Q)$ space, $\Theta(Q (\log Q) ^ 2)$ time で解くアルゴリズムを解説します。
Static Rectangle Add Rectangle Sum の解法
追記 (2022/05/10) : Rectangle Add Rectangle Sum における解法のようにクエリを 4 分割すれば、最後の遅延セグメント木パートを (通常の) Binary Indexed Tree に代えることができ、定数倍で本解法よりも高速であろうことを確認しました。
$\mathrm{add}$ クエリおよび $\mathrm{sum}$ クエリを次のように分割します。
この分割により、$\mathrm{add}(v,l, \infty,d,u)$ の形の $\mathrm{add}$ クエリおよび $\mathrm{sum}(-\infty,r,d,u)$ の形の $\mathrm{sum}$ クエリしか存在しないようなケースに帰着できました。ここで、帰着後の問題のクエリ数は、元のクエリ数の定数倍 (ちょうど $2$ 倍) に収まっていることに注意します。
結論を先に書くと、この簡単化された問題は $x$ 方向の平面走査により区間一次関数加算・区間和取得の遅延伝播セグメント木で解くことが出来ます。
以降、$\mathrm{add'}(v,l,d,u)$ で $\mathrm{add}(v,l, \infty,d,u)$ を、$\mathrm{sum'}(r,d,u)$ で $\mathrm{sum}(-\infty,r,d,u)$ を表すことにします。
$\mathrm{sum'}(x,\ast,\ast)$ の計算結果に影響するのは、$l \lt x$ を満たす $\mathrm{add'}(\ast,l,\ast,\ast)$ クエリに限られます。そして、$l \lt x$ のとき、任意の整数 $y$ に対して $\mathrm{add'}(v,l,y,y+1)$ クエリの $\mathrm{sum'}(x,y,y+1)$ への寄与は $v(x-l) = vx - vl$ という $x$ に関する一次関数の形で書くことが出来ます (下図参照)。また、$l = x$ の場合もこの寄与の式は正しいです。
ここで、$\mathrm{add'}(\ast,x,\ast,\ast)$ や $\mathrm{sum'}(x,\ast,\ast)$ を $x$ の昇順に並び替えて処理することにすれば (平面走査)、$\mathrm{sum'}$ クエリに対する答えを保存しつつ、上記の $l \lt x$ (あるいは、$l\leq x$) という制約を外すことができます。先の議論から、タイブレークは任意に定めてよいです。
従って、今までに見た $\mathrm{add'}$ クエリの $\mathrm{sum'}(x,y,y+1)$ への寄与の総和を $w _ y (x)$ と書くことにすれば、各クエリは次のように処理できます。
$\mathrm{add'}(v,l,d,u)$ の場合:
全ての $l \leq y \lt d$ を満たす整数 $y$ に対して $w _ y(x) \leftarrow w _ y(x) + vx - vl$ と更新する。
$\mathrm{sum'}(r,d,u)$ の場合:
$\displaystyle \sum _ {y = d} ^ {u - 1} (w _ y(r)) = \left(\sum _ {y = d} ^ {u - 1} w _ y \right) (r)$ を計算する。
これらの操作は、予めクエリに現れる $y$ 座標を列挙して座標圧縮を行っておくことにより、区間一次関数加算・区間和取得の遅延伝播セグメント木により各々 $\Theta(\log Q)$ time で処理できます。
ここで、区間一次関数加算は $(ax + b) + (cx + d) = (a + c)x + (b + d)$ のような操作を指し、区間等差数列加算とは異なるものです。混同しないよう注意してください。
前処理の座標圧縮やクエリのソートなどは $\Theta(Q)$ space, $\Theta(Q \log Q)$ time で処理できるので、全体 $\Theta(Q)$ space, $\Theta(Q \log Q)$ time で Static Rectangle Add Rectangle Sum を解くことが出来ました。
実装
私のライブラリへのリンクで代えさせて頂きます。(追記 (2022/05/10) : より定数倍のよい Binary Indexed Tree を用いた実装に差し替えました)
Rectangle Add Rectangle Sum の解法
$\mathrm{add}$ や $\mathrm{sum}$ が入り混じっている場合、先の解法のようにクエリをうまく並び替えることは難しいです。
以下のようにクエリをさらに分割し、さらに計算しやすい形にします。
この分割により、$\mathrm{add}(v,l, \infty,d,\infty)$ の形の $\mathrm{add}$ クエリおよび $\mathrm{sum}(-\infty,r,-\infty,u)$ の形の $\mathrm{sum}$ クエリしか存在しないようなケースに帰着できました。ここで、帰着後の問題のクエリ数は、元のクエリ数の定数倍 (ちょうど $4$ 倍) に収まっていることに注意します。
以降、$\mathrm{add''}(v,l,d)$ で $\mathrm{add}(v,l, \infty,d,\infty)$ を、$\mathrm{sum''}(r,u)$ で $\mathrm{sum}(-\infty,r,-\infty,u)$ を表すことにします。
$\mathrm{sum''}(x,y)$ の計算結果に影響するのは、$l \lt x$ かつ $d \lt y$ を満たす $\mathrm{add''}(\ast,l,d)$ クエリに限られます。そして、$l \lt x$ かつ $d \lt y$ のとき、$\mathrm{add''}(v,l,d)$ クエリの $\mathrm{sum''}(x,y)$ への寄与は $v(x-l)(y-d) = vxy - vdx-vly+vld$ であり、即ち $f(x,y)=axy+bx+cy+d$ という形の関数で書くことが出来ます (下図参照)。
従って、この簡単化された問題は $axy+bx+cy+d$ という形をした $x,y$ を変数とする関数を点の重みとする Point Add Rectangle Sum に帰着することが出来ます。
Point Add Rectangle Sum は例えば必要なところだけ作る 2D BIT などを用いることで $\Theta(Q \log Q)$ space, $\Theta(Q (\log Q) ^ 2)$ time で解くことが出来るので、Rectangle Add Rectangle Sum も同じ計算量オーダーで解くことが出来ました。
ところで、Point Add Rectangle Sum における重みの計算コストが通常の整数の加算の場合と比較して単純計算で $4$ 倍であり、クエリ数も $4$ 倍なので、定数倍はかなり大きいです。あとに示す実装例で $10 ^ 5$ クエリのランダムケースで計測すると $1$ 秒以上掛かっていました。
実装
私のライブラリへのリンクで代えさせて頂きます。
おわりに
Rectangle Add Rectangle Sum の方は Point Add Rectangle Sum に帰着してしまえば最悪 Library Checker から借りられるけど、Static の方は予めライブラリを作っておかないとかなり苦しい気がする... (Static の方もクエリを $4$ 分割の解法なら割と軽めでした)
