以下な長方形区域についての「総和」の最大値も簡単に求めることができます。おわりに競技プログラミングを始めてから、累積和を扱えるようになると、解ける問題の幅が一気に広がって楽しくなります。素敵な累積和ライフを!最後に累積和に関連する発展的トピックを紹介して締めます。累積和と並んで、競技プログラミングで初期に学ぶ楽しい手法です。(最後に、最終的な区間の値をまとめて知る)というクエリを高速に扱うことのできる手法になっています。いもす法という名前の由来となったいもすさんによる解説記事を参考にしていただけたらと思います。区間に関する問題において、累積和以外にも検討したい手法として、しゃくとり法があります。ある種の条件設定においては〜という条件を満たす区間を数え上げよ〜という条件を満たす区間の長さの最大値を求めよといった問題を効率良く解くことのできるアルゴリズムになっています。詳しくはしゃくとり法を参考にしていただけたらと思います。今回は累積和は「配列の区間の総和を求めるクエリを爆速に処理する」アルゴリズムとして紹介しました。割ったあまりを求めるクエリを爆速処理するといった場面にも自然に使うことができます。和を求めるクエリを爆速処理するというのもあります。抽象的には群と呼ばれる構造全般に対して適用することができます。これは上記のいもす法などにも言えることです。柔軟に多彩な応用ができるととても楽しいです。今回の問題設定では、「配列の値は常に不変」という状態を扱っていました。実際には配列のある値が更新される配列内のある区間の総和を求めたいという二種類のクエリが入り乱れる場面も多々あります。セグメントツリーと呼ばれるデータ構造を用いるとピッタリです。ローリングハッシュ文字列検索問題において超基本となる手法です。どこに登場するのかを検索する問題を考えてみましょう。一致するかどうかを調べることになります。計算時間が必要になります。実はローリングハッシュと呼ばれる手法と、累積和のような手法を組合せることで上手に検索することができます。求めることができるようになります。計算時間で検索できるようになりました。読んでいただけたらと思います。g(i)$という形をした遷移式が登場することが多々あります。配列の累積和をとることで、この部分の計算を効率化することができます。人であり、多くのサービスに付随するデータとして典型的なサイズ感だと思います。