cumulative sum

ソースコード

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5// CumulativeSum
 6namespace titan23 {
 7    template<typename T>
 8    class CumulativeSum {
 9      private:
10        int n;
11        vector<T> acc;
12
13      public:
14        CumulativeSum() {}
15        CumulativeSum(vector<T> &a, T e) : n((int)a.size()), acc(n+1, e) {
16            for (int i = 0; i < n; ++i) {
17                acc[i+1] = acc[i] + a[i];
18            }
19        }
20
21        T pref(const int r) const {
22            assert(0 <= r && r <= this->n);
23            return acc[r];
24        }
25
26        T all_sum() const {
27            return acc.back();
28        }
29
30        T sum(const int l, const int r) const {
31            assert(0 <= l && l <= r && r <= this->n);
32            return acc[r] - acc[l];
33        }
34
35        T prod(const int l, const int r) const {
36            assert(0 <= l && l <= r && r < this->n);
37            return acc[r] - acc[l];
38        }
39
40        T all_prod() const {
41            return acc.back();
42        }
43
44        int len() const {
45            return n;
46        }
47
48        void print() const {
49            cout << '[';
50            for (int i = 0; i < n-1; ++i) {
51                cout << acc[i] << ", ";
52            }
53            if (n > 0) cout << acc.back();
54            cout << ']' << endl;
55        }
56    };
57}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/cumulative_sum.cpp