累積和

今回はpaiza 累積和メニューセクショ5【二次元累積和】を解説します。 整数の要素をもつ、h行 w列の二次元配列aの、左上の要素をa[sy][sx], 右下の要素をa[gy][gx]としたときに出来 ...

今回はpaiza 累積和メニューセクショ4【区間内の個数(文字列)】を解説します。 n文字の文字列strの、任意の区間内の"b"の数はいくつか？を出力する問題です。 本記事で使用しているアルゴリズムや ...

今回はpaiza 累積和メニューセクショ3【区間内の個数】を解説します。 n個の整数の要素からなる配列aがあり、任意の区間内の偶数の数はいくつか？を出力する問題です。 本記事で使用しているアルゴリズム ...

今回はpaiza 累積和メニューセクショ2【連続する N 個の和の最大値】を解説します。 n個の整数の要素からなる配列aがあり、その中で連続する k個の整数の和が最大の値はいくつか？を出力する問題です ...

今回はpaiza 累積和メニューセクション1【区間の和】を解説します。 セクション1は、累積和から区間和を求める問題です。 本記事で使用しているアルゴリズムやメソッドについて 解答例で使っているアルゴ ...

いもす法とは いもす法は累積和を応用したアルゴリズムです。 区間の入口と出口で要素分の加算・減算を行って累積和を求めることで、任意の区間に要素がいくつ収まっているかを高速に計算することが出来ます。 い ...

累積和とは 累積和(prefix sum)は、配列の任意の区間の総和を求めるためのアルゴリズムです。 繰り返し処理を使うと大きな計算量になってしまう区間の計算問題を、適切な前処理を行うことによって高速 ...