C++ 累積和

累積和は、配列の一部の範囲の合計を出すやつです。何回も合計を出す場合に効率化できます。最初に合計を入れる配列を用意して、順番にその位置までの合計を入れていきます。あとはそれを参照するだけで合計出せます。

サンプルコード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> vec = {1, 3, 5, 7, 9, 11, 13};
  vector<int> sum(vec.size());
  int s = 0;
  for (int i = 0; i < vec.size(); ++i) {
    s += vec[i];
    sum[i] = s;
  }
  // 3～5までの合計（7 + 9 + 11）
  cout << sum[5] - sum[3 - 1] << endl;
}

結果

27