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

二項差での累積和

できること

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

  A:     1   4   2   8   2   9
  増分 --> 3  -->  6  -->  7  -->
  S:  0  0   3   3   9   9  16
  

計算量

$O(N)$

使い方

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

Verified with

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

Code

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

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

Back to top page