競プロでよく出る区間和問題の解き方まとめ

2020年3月6日その他区間和, テーマ記事, 競プロ, 区間, 累積和, imos法, 二次元区間和

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

  • 前処理:\(O(N)\)
  • クエリ:\(O(1)\)

で処理ができます。

二次元の区間和

二次元の場合でも、同様に累積和を用いることで処理することができます。\(H×W\) の区間なら、

  • 前処理:\(O(HW)\)
  • クエリ:\(O(1)\)

となります。

区間の更新がある場合

仮に数列が1つでも途中で変化する場合は、累積和を更新することになるので、毎回 \(O(N)\) だけ時間がかかってしまいます。

そこで、セグメント木BITなどの区間に強いデータ構造を用いると、

  • 更新:\(O(\log N)\)
  • クエリ:\(O(\log N)\)

で処理ができます。

区間への加算をする時

「ある一定区間 [L, R) 全体に、x を加えたい」という操作をたくさん行う場合、一回あたりに \(O(N)\) 程度の計算量がかかってしまうので、Q 回行うと \(O(QN)\)だけかかります。

クエリの前に加算が終了する:imos 法(区間への加算)

imos 法と呼ばれる累積和を利用したアルゴリズムを利用することで、全体で \(O(Q+N)\) で計算することができます。

詳しくは本家解説:いもす法 – いもす研 (imos laboratory)

クエリと加算が入り乱れている:遅延評価セグメント木や区間加算対応BIT

区間に対する更新処理に対応させたセグメント木BITを用いれば、

  • 更新:\(O(\log N)\)
  • クエリ:\(O(\log N)\)

で処理ができます。

練習問題

1次元の累積和

2次元の累積和