累積和
(library/dp/cumulative_sum/cumulative_sum.hpp)

• View this file on GitHub
• Last update: 2026-01-15 10:11:56+09:00
• Include: #include "library/dp/cumulative_sum/cumulative_sum.hpp"

累積和

できること

• 累積和の数列を返す。 $S_i = \sum A[0, i)$

  A:    1   4   2   8   2   9
  S: 0  1   5   7  15  17  26
  

半開区間 $[l, r)$ の和は、次のように求められる。

$\displaystyle\sum_{j=l}^{r-1} A_j = S_r - S_l$

計算量

$O(N)$

使い方

vector<long long> S = cumulative_sum(A);

Verified with

• 累積和のテスト (tests/dp.cumulative_sum.cumulative_sum.test.cpp)

Code

#pragma once
vector<long long> cumulative_sum(const vector<long long> &A) {
    int N = A.size();
    vector<long long> S(N + 1);
    for (int i = 0; i < N; ++i) S[i + 1] = S[i] + A[i];
    return S;
}

#line 2 "library/dp/cumulative_sum/cumulative_sum.hpp"
vector<long long> cumulative_sum(const vector<long long> &A) {
    int N = A.size();
    vector<long long> S(N + 1);
    for (int i = 0; i < N; ++i) S[i + 1] = S[i] + A[i];
    return S;
}

Back to top page