This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/cumulative_sum.hpp"
cumulative_sum(d)
: 数列 $\mathrm d$ で初期化する。sum(l, r)
: $\mathrm d_l + \mathrm d_{l+1} + \cdots +\mathrm d_{r-1}$ を求める。cumulative_sum(d)
: $\mathcal O(N)$sum(l, r)
: $\mathcal O(1)$#pragma once
#include <vector>
template <typename T>
struct cumulative_sum {
int n;
std::vector<T> cumsum;
cumulative_sum() {
}
cumulative_sum(std::vector<T>& d) : n(d.size()), cumsum(n + 1) {
for (int i = 0; i < n; i++) {
cumsum[i + 1] = cumsum[i] + d[i];
}
}
T sum(int l, int r) {
// 0-indexed
// [l, r)
assert(0 <= l);
assert(l <= r);
assert(r <= n);
return cumsum[r] - cumsum[l];
}
};
#line 2 "datastructure/cumulative_sum.hpp"
#include <vector>
template <typename T>
struct cumulative_sum {
int n;
std::vector<T> cumsum;
cumulative_sum() {
}
cumulative_sum(std::vector<T>& d) : n(d.size()), cumsum(n + 1) {
for (int i = 0; i < n; i++) {
cumsum[i + 1] = cumsum[i] + d[i];
}
}
T sum(int l, int r) {
// 0-indexed
// [l, r)
assert(0 <= l);
assert(l <= r);
assert(r <= n);
return cumsum[r] - cumsum[l];
}
};