二項差での累積和 反転
(library/dp/cumulative_sum/cumulative_sum_rev_diff.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_diff.hpp"

二項差での累積和 反転

できること

• 2項ごとでの、逆向きの累積和の数列を返す。

  A:    1   4   2   8   2   9
  増分　 <--  2  <--  6  <--  9  <--
  R:   17  17  15  15   9   9  0
  

計算量

$O(N)$

使い方

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

Verified with

• 二項差での累積和 反転のテスト (tests/dp.cumulative_sum.cumulative_sum_rev_diff.test.cpp)

Code

#pragma once
template <typename T>
vector<long long> cumulative_sum_rev_diff(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];
        if (i & 1) R[i] += abs((i + 1 < N ? A[i + 1] : 0) - A[i]);
    }
    return R;
}

#line 2 "library/dp/cumulative_sum/cumulative_sum_rev_diff.hpp"
template <typename T>
vector<long long> cumulative_sum_rev_diff(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];
        if (i & 1) R[i] += abs((i + 1 < N ? A[i + 1] : 0) - A[i]);
    }
    return R;
}

Back to top page