Hack109のブログ

ネットワーク、プログラミングなどで学んだことや試してみたことを投稿していきます。

一次元の累積和について【プログラミング】【競プロ】

はじめに

一次元の累積和は、このような問題で使用できます。

【例題】
N日間にわたって開催された展示会について、i日目にはAi人が来場しました。 この展示会について、Q個の質問に答えるプログラムを作成してください。

  • 展示会におけるL1日目からR1日目までの総来場数は?  
      ・・・  
  • 展示会におけるLQ日目からRQ日目までの総来場数は?   

制約

  • 1 <= N <= 100000
  • 1 <= A <= 10000
  • 1 <= L <= R <= N

累積和(一次元)の使いどころ

一列に並べられた数値について、x番目からy番目に格納されている値の総数を算出するときに使用できます。

累積和(一次元)のアルゴリズム

i日間の展示会の総来場数を下記とします。
累積和のアルゴリズムをしない場合、4日目から8日目の総来場数を求める場合は、
A4+A5+A6+A7+A8 で算出されます。

例題ではQ個の質問に答えるプログラムを作成することを求められています。 質問が1つならともかく、複数の質問に答えなければならないとなると、L,R日目に入力される値によっては実行時間が大きくなります。 (1つ目の質問が1日目から17日目、2つ目の質問が2日目から16日目みたいに…)

そこで、累積和のアルゴリズムを用いて効率的に算出していきます。

累積和により、i日目の総来場数を算出する。

L日目からR日目までの総来場数を算出する前に、i日目までの累計来場者数Siをあらかじめ計算しておきます。

L日目~R日目の総来場数は..?

i日目までの累計来場者数が分かれば、L日目からR日目の総来場者数は下記の計算で算出できます。

(R日目までの累計来場者数SR) - (L-1日目までの累計来場者数SL-1)

あらかじめi日目までの累計来場者数が算出されていることで、 例題のようにL日目からR日目までの総来場者数をQ個質問されていても、 総来場者数の計算は一度の計算で済みます。

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int N = 0;
    int Q = 0;


    cin >> N >> Q;


    int offset = 1;
    vector<int> A(N + offset, 0);
    vector<int> S(N + offset, 0);
    vector<int> L(Q + offset, 0);
    vector<int> R(Q + offset, 0);

    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int j = 1; j <= Q; j++) cin >> L[j] >> R[j];

    for (int i = 1; i <= N; i++) S[i] = S[i - 1] + A[i];

    for (int j = 1; j <= Q; j++) {
        cout << S[R[j]] - S[L[j] - 1] << endl;
    }

    return 0;
}

さいごに

まとめ

一次元の累積和のアルゴリズムは、一列に並べられた数値について、x番目からy番目に格納されている値の総数を算出するときに使用できます。

今後

今回は一次元の累積和についての解説でしたが、次は二次元の累積和についても取り上げたいと思います。