累積和は、配列の一部の範囲の合計を出すやつです。何回も合計を出す場合に効率化できます。最初に合計を入れる配列を用意して、順番にその位置までの合計を入れていきます。あとはそれを参照するだけで合計出せます。
サンプルコード
#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