1次元累積和
(datastructure/cumulativesum/cumulativesum.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "datastructure/cumulativesum/cumulativesum.hpp"

概要

静的な配列に対する区間和クエリに答える.

計算量

• 構築 : $O(n)$
• クエリ : $O(1)$

使用例

• CumulativeSum<int> acc(v) : vで累積和を構築.
• acc.query(l, r) : 半開区間$[l, r)$のクエリ.
• acc[k] : 元の配列の$k$要素目.
• acc.print() : 累積和の中身をデバッグ出力.

Verified with

• test/yosupo/staticrangesum.test.cpp

Code

/**
* @brief 1次元累積和
* @docs docs/datastructure/cumulativesum/cumulativesum.md
*/

template <typename T>
struct CumulativeSum {
    int sz;
    vector<T> data;
    CumulativeSum(const vector<T> &v, const T margin = 0)
        : sz(v.size()), data(1, margin) {
        for (int i = 0; i < sz; ++i) data.emplace_back(data[i] + v[i]);
    }
    T query(const int &l, const int &r) const {
        if (l >= r) return 0;
        return data[min(r, sz)] - data[max(l, 0)];
    }
    T operator[](const int &k) const {
        return query(k, k + 1);
    }
    void print() {
        for (int i = 0; i < sz; ++i) cerr << data[i] << ' ';
        cerr << endl;
    }
};

#line 1 "datastructure/cumulativesum/cumulativesum.hpp"
/**
* @brief 1次元累積和
* @docs docs/datastructure/cumulativesum/cumulativesum.md
*/

template <typename T>
struct CumulativeSum {
    int sz;
    vector<T> data;
    CumulativeSum(const vector<T> &v, const T margin = 0)
        : sz(v.size()), data(1, margin) {
        for (int i = 0; i < sz; ++i) data.emplace_back(data[i] + v[i]);
    }
    T query(const int &l, const int &r) const {
        if (l >= r) return 0;
        return data[min(r, sz)] - data[max(l, 0)];
    }
    T operator[](const int &k) const {
        return query(k, k + 1);
    }
    void print() {
        for (int i = 0; i < sz; ++i) cerr << data[i] << ' ';
        cerr << endl;
    }
};

Back to top page