階差数列
(library/sequence/difference_sequence.hpp)

• View this file on GitHub
• Last update: 2026-01-07 21:05:45+09:00
• Include: #include "library/sequence/difference_sequence.hpp"

階差数列

できること

• 各項の差の数列を返す

  A: 1   4   2   8   2   9
  D:   3  -2   6  -6   7
  

計算量

$O(N)$

使い方

vector<long long> diff = difference_sequence(A);

Verified with

• 階差数列のテスト (tests/sequence.difference_sequence.test.cpp)

Code

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

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

Back to top page