CumulativeSum
(Data_structure/CumulativeSum.hpp)

• View this file on GitHub
• Last update: 2023-01-27 17:37:24+09:00
• Include: #include "Data_structure/CumulativeSum.hpp"

累積和

コンストラクタ

CumulativeSum<T> cum(vector<T> v)

• vの内容で初期化

計算量

• $O(N)$

sum

(1) T cum.sum(int r)
(2) T cum.sum(int l, int r)

• (1): a[0] + ... + a[r-1]を返す
• (2): a[l] + ... + a[r-1]を返す

制約

• (1): $0 \leq r \leq N$
• (2): $0 \leq l \leq r \leq N$

計算量

• $O(1)$

Verified with

• Test/yosupo-Static-Range-Sum.test.cpp

Code

template<class T> struct CumulativeSum {
    int n;
    vector<T> data; 
    bool builded = false;
    CumulativeSum(int n) : n(n), data(n + 1) {}
    CumulativeSum(const vector<T> &v) : n(v.size()), data(n + 1) {
        for (int i = 0; i < n; i++) {
            data[i + 1] = v[i];
        }
    }

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

    T sum(int r) {
        if (!builded) build();
        assert(0 <= r && r <= n);
        return data[r];
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) - sum(l);
    }

};

#line 1 "Data_structure/CumulativeSum.hpp"
template<class T> struct CumulativeSum {
    int n;
    vector<T> data; 
    bool builded = false;
    CumulativeSum(int n) : n(n), data(n + 1) {}
    CumulativeSum(const vector<T> &v) : n(v.size()), data(n + 1) {
        for (int i = 0; i < n; i++) {
            data[i + 1] = v[i];
        }
    }

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

    T sum(int r) {
        if (!builded) build();
        assert(0 <= r && r <= n);
        return data[r];
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) - sum(l);
    }

};

Back to top page