BIT 2D RangeAdd RangeSum

個人的メモ

イメージは 1 次元の範囲加算と範囲総和を BIT で行うやつ と 2 次元 BIT を組み合わせた感じ. $xy$ の項, $x$ の項, $y$ の項, 定数項 に分けてそれぞれを $2$ 次元 BIT で処理する. 特に大したことはやっておらず式を書き下すと分かる.
計算量は最悪計算量が線形である quadtree と比べて高速.
多次元領域の min や update などのクエリを polylog で処理するアルゴリズムはわかっていないそう.