This documentation is automatically generated by online-judge-tools/verification-helper
#include "data_structure/cumulative_sum.hpp"
使い方
sum(l, r)
で A[l] + A[l + 1] + ... + A[r - 1]
を返すn
とすると、$[0, n)$ への加算ができる(加算しうる半開区間の右端の値を入力する)imos(l, r, z)
で $ [l, r) $ に $ z $ を加算build()
で構築rui.get(p)
でアクセス#pragma once
template <class T> struct CumulativeSum {
int n;
std::vector<T> seg;
CumulativeSum() = default;
CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}
CumulativeSum(std::vector<T>& a) {
n = (int)a.size();
seg.assign(n + 1, T(0));
for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
}
// [l, r)
T sum(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
return seg[r] - seg[l];
}
// A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
void imos(int l, int r, T x = T(1)) {
assert(0 <= l and l <= r and r <= n);
seg[l] += x;
seg[r] -= x;
}
void build() {
for (int i = 0; i < n; i++) seg[i + 1] += seg[i];
}
// return A[p]
T get(int p) const {
assert(0 <= p and p < n);
return seg[p];
}
std::vector<T> make_vector() { return seg; }
};
#line 2 "data_structure/cumulative_sum.hpp"
template <class T> struct CumulativeSum {
int n;
std::vector<T> seg;
CumulativeSum() = default;
CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}
CumulativeSum(std::vector<T>& a) {
n = (int)a.size();
seg.assign(n + 1, T(0));
for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
}
// [l, r)
T sum(int l, int r) const {
assert(0 <= l and l <= r and r <= n);
return seg[r] - seg[l];
}
// A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
void imos(int l, int r, T x = T(1)) {
assert(0 <= l and l <= r and r <= n);
seg[l] += x;
seg[r] -= x;
}
void build() {
for (int i = 0; i < n; i++) seg[i + 1] += seg[i];
}
// return A[p]
T get(int p) const {
assert(0 <= p and p < n);
return seg[p];
}
std::vector<T> make_vector() { return seg; }
};