1次元累積和
(Datastructure/static1dsum.hpp)

• View this file on GitHub
• Last update: 2025-01-21 17:35:19+09:00
• Include: #include "Datastructure/static1dsum.hpp"

概要

1次元累積和

+演算を他の演算に変えたくなった時

逆元があれば良い。 add, prod(y, x), prod(sy, sx, ty, tx) の + , - , += , -= を全て変更する。

コンストラクタ

template<typename T> static1dsum(int n) … T : 値の型。 [0, n) の配列を作る. 初期値は0

• 計算量 $O(n)$

template<typename T> static1dsum(vec<T> dat)… datをコピーする。

• 計算量 $O(n)$

関数

基本、計算量は $O(1)$

・1点加算/区間取得

• void add(int i, T v) … A[i] += v

• void build() … 累積和を計算する。以降add不可能。また、buildを呼ぶ前はget.prod不可。(どちらも、assertが反応する)
  • 計算量 $O(n)$
• T prod(int l, int r) … [l, r)の範囲領域の和を返す。半開区間

Verified with

• verify/Datastructure_static1dsum.test.cpp

Code

TT struct static1dsum {
    int n;
    vec<T> dat;
    bool built = false;

    static1dsum(int n = 0) : static1dsum(vec<T>(n, T())) {}

    static1dsum(vec<T> dat) : n(dat.size()), dat(dat) {}

    void add(int i, T x) {
        assert(built == false);
        dat[i] += x;
    }

    void build() {
        assert(built == false);
        rep(i, 0, n - 1) dat[i + 1] += dat[i];
        built = true;
    }

    T get(int p) const {
        assert(built);
        assert(0 <= p && p < n);
        T res = dat[p];
        if(p) res -= dat[p-1];
        return res;
    }

    T prod(int l, int r) const {
        assert(built);
        assert(0 <= l && r <= n);
        assert(l <= r);
        if(l == r) return 0;
        T res = dat[r - 1];
        if (l) res -= dat[l - 1];
        return res;
    }

    T all_prod() const {
        assert(built);
        return dat[n-1];
    }
};
/*
@brief 1次元累積和
@docs doc/static1dsum.md
*/

#line 1 "Datastructure/static1dsum.hpp"
TT struct static1dsum {
    int n;
    vec<T> dat;
    bool built = false;

    static1dsum(int n = 0) : static1dsum(vec<T>(n, T())) {}

    static1dsum(vec<T> dat) : n(dat.size()), dat(dat) {}

    void add(int i, T x) {
        assert(built == false);
        dat[i] += x;
    }

    void build() {
        assert(built == false);
        rep(i, 0, n - 1) dat[i + 1] += dat[i];
        built = true;
    }

    T get(int p) const {
        assert(built);
        assert(0 <= p && p < n);
        T res = dat[p];
        if(p) res -= dat[p-1];
        return res;
    }

    T prod(int l, int r) const {
        assert(built);
        assert(0 <= l && r <= n);
        assert(l <= r);
        if(l == r) return 0;
        T res = dat[r - 1];
        if (l) res -= dat[l - 1];
        return res;
    }

    T all_prod() const {
        assert(built);
        return dat[n-1];
    }
};
/*
@brief 1次元累積和
@docs doc/static1dsum.md
*/

Back to top page