ei1333's page

長方形の和集合

説明

長方形の和集合を効率よく求めるデータ構造。長方形の右上の点の追加を対数時間でサポートする。第一象限のみなので象限を増やす場合は適切に処理する必要がある。

使い方

• $\mathrm{addPoint}(x, y)$: 右上の点 $(x, y)$ の長方形を追加する。
• $\mathrm{getSum}()$: 現在の長方形群の和集合の面積を求める。

計算量

$O(\log n)$

実装例