競プロでよく出る区間和問題の解き方まとめ
Contents
区間の更新がない場合
区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。
一次元の区間和
累積和を用いることで、
- 前処理：\(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次元の累積和
- 全国統一プログラミング王決定戦本戦 A – Abundant Resources
- AOJ 0516 – 最大の和 (JOI 2006 本選 A)
- [AtCoder] ABC 084 D – 2017-like Number
- [AtCoder] AGC 023 A – Zero-Sum Ranges