累積和 反転
(library/dp/cumulative_sum/cumulative_sum_rev.hpp)

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

累積和 反転

できること

• 逆向きの累積和の数列を返す。$R_i =$「$A_i$から右全部の和」

  A:  1   4   2   8   2   9
  R: 26  25  21  19  11   9  0
  

累積和 $S$ と合わせて、全区間の和は次のように求められる。

$\displaystyle\sum_{j=0}^{i-1} + \displaystyle\sum_{j=i}^{last} = S_i + R_i$

計算量

$O(N)$

使い方

vector<long long> R = cumulative_sum_rev(A);

Verified with

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

Code

#pragma once
template <typename T> vector<long long> cumulative_sum_rev(const vector<T> &A) {
    int N = A.size();
    vector<long long> R(N + 1);
    for (int i = N - 1; i >= 0; --i) R[i] = R[i + 1] + A[i];
    return R;
}

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

Back to top page