Dynamic 2D-BIT メモ

何がしたい?

H*Wの二次元配列に対し、一点更新(加算)、長方形和取得

(H,W<=10^18、更新する点の個数<=10^6)

 

実装方法

BITを持つ配列でBITを作る

全ての座標の情報を持つことはできない→必要な部分だけ作る

更新する点の座標のリストを持ち、(x,y)でソートしindexを振る(先に更新クエリを先読みする必要がある、取得クエリの端点は不要)

BITを持つ各配列には、(点P_iからP_jまでを見たときのBIT)を対応させ、この配列でBITを作る

中のBITも座圧しておく(ysのindexでやってる)

クエリ処理は通常のBITと同じことを2回やる

 

 

verify:https://judge.yosupo.jp/problem/rectangle_sum