【要約】Python 累積和入門 その３ [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
データ処理において、大量の区間加算クエリを処理する際に計算量が爆発する問題がある。開発者が $N$ 個の要素を持つ配列に対し、$Q$ 回の区間加算を行う場合、素朴な実装では以下の課題に直面する。
- ・各操作で区間内の全要素を走査するため、最悪計算量が $O(NQ)$ となる。
- ・$N=10^5, Q=10^5$ といった大規模な制約下では、実行時間制限（TLE）に抵触する。
- ・逐次的な加算処理が、全体のパフォーマンスを著しく低下させる。
// Approach
差分配列（Difference Array）を用いることで、計算量を $O(N+Q)$ に削減するアプローチをとる。区間の全要素を更新するのではなく、変化点のみを記録する手法である。
具体的な手順は以下の通りである。
具体的な手順は以下の通りである。
- ・区間の開始位置 $l$ に加算値を記録する。
- ・区間の終了位置 $r$ に減算値を記録する。
- ・すべてのクエリ完了後、差分配列に対して左から累積和を計算する。
- ・差分と累積和が互いに逆演算であることを利用し、目的の配列を復元する。
// Result
いもす法を導入することで、クエリ処理の計算量を $O(1)$ に抑え、全体の計算量を $O(N+Q)$ まで低減できる。これにより、大規模なデータセットに対しても実用的な速度で処理が可能となる。具体的な成果として以下の応用が挙げられる。
- ・カフェの入退場記録から、最大同時滞在人数を高速に算出する。
- ・録画番組のスケジュールから、録画の重複有無を判定する。
- ・数直線上の線分が $K$ 個以上重なる座標の個数を特定する。
Senior Engineer Insight
> いもす法は、静的なデータセットに対する一括処理において極めて強力である。しかし、実戦投入時には以下の制約を考慮すべきだ。
- ・クエリと参照が交互に発生する動的な環境では、セグメント木等のより高度なデータ構造が必要となる。
- ・座標の範囲が極端に広い場合は、メモリ消費を抑えるために座標圧縮を併用せよ。
- ・計算量の劇的な改善は、大規模トラフィックを扱うシステムにおいて不可欠な視点である。