累積和
(data_structure/cumulative_sum.hpp)

• View this file on GitHub
• Last update: 2023-03-17 17:11:39+09:00
• Include: #include "data_structure/cumulative_sum.hpp"

使い方

1. ある配列の区間和を求める場合
   • コンストラクタ引数に配列を入力
   • sum(l, r)で A[l] + A[l + 1] + ... + A[r - 1] を返す
2. imos法のように使う場合
   • コンストラクタ引数に入力した値をnとすると、$[0, n)$ への加算ができる(加算しうる半開区間の右端の値を入力する)
   • imos(l, r, z)で $ [l, r) $ に $ z $ を加算
   • build()で構築
   • rui.get(p)でアクセス

Verified with

• verify/aoj_other/aoj_0360.test.cpp
• verify/aoj_other/aoj_2286.test.cpp
• verify/lc_data_structure/lc_static_range_sum.test.cpp

Code

#pragma once

template <class T> struct CumulativeSum {
    int n;
    std::vector<T> seg;

    CumulativeSum() = default;

    CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}

    CumulativeSum(std::vector<T> &a) {
        n = (int)a.size();
        seg.assign(n + 1, T(0));
        for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
    }

    // [l, r)
    T sum(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return seg[r] - seg[l];
    }

    // A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
    void imos(int l, int r, T x = T(1)) {
        assert(0 <= l and l <= r and r <= n);
        seg[l] += x;
        seg[r] -= x;
    }

    void build() {
        for (int i = 0; i < n; i++) seg[i + 1] += seg[i];
    }

    // return A[p]
    T get(int p) const {
        assert(0 <= p and p < n);
        return seg[p];
    }

    // output
    friend std::ostream &operator<<(std::ostream &os, const CumulativeSum &A) {
        os << "n = " << A.n << "\n";
        for (int i = 0; i <= A.n; i++) os << A.seg[i] << " \n"[i == A.n];
        return os;
    }
};

#line 2 "data_structure/cumulative_sum.hpp"

template <class T> struct CumulativeSum {
    int n;
    std::vector<T> seg;

    CumulativeSum() = default;

    CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}

    CumulativeSum(std::vector<T> &a) {
        n = (int)a.size();
        seg.assign(n + 1, T(0));
        for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
    }

    // [l, r)
    T sum(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return seg[r] - seg[l];
    }

    // A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
    void imos(int l, int r, T x = T(1)) {
        assert(0 <= l and l <= r and r <= n);
        seg[l] += x;
        seg[r] -= x;
    }

    void build() {
        for (int i = 0; i < n; i++) seg[i + 1] += seg[i];
    }

    // return A[p]
    T get(int p) const {
        assert(0 <= p and p < n);
        return seg[p];
    }

    // output
    friend std::ostream &operator<<(std::ostream &os, const CumulativeSum &A) {
        os << "n = " << A.n << "\n";
        for (int i = 0; i <= A.n; i++) os << A.seg[i] << " \n"[i == A.n];
        return os;
    }
};

Back to top page