prefix_sum.hpp¶
Static half-open range sums over an additive group. Construction stores cumulative sums with an explicit zero at position zero. The sum on [left,right) is the difference of the two boundary prefixes, so each query needs no tree traversal and preserves the value type exactly.
Verified by static_range_sum.
预处理一维前缀和，以常数时间回答静态区间和；适合数组不再修改、但区间求和很多的题目。
Implementation¶
#ifndef NOYA_PREFIX_SUM_HPP
#define NOYA_PREFIX_SUM_HPP 1
/// @complexity Time: O(n) construction and O(1) per range-sum query.
/// Space: O(n).
#include <cassert>
#include <iterator>
#include <vector>
namespace noya {
/// @brief Static half-open range sums over an additive group.
/// Construction stores cumulative sums with an explicit zero at position zero.
/// The sum on [left,right) is the difference of the two boundary prefixes, so
/// each query needs no tree traversal and preserves the value type exactly.
template <class T> class prefix_sum {
std::vector<T> prefix_ = {T{}};
public:
prefix_sum() = default;
template <class Iterator> prefix_sum(Iterator first, Iterator last) {
for (; first != last; ++first) {
prefix_.push_back(prefix_.back() + *first);
}
}
explicit prefix_sum(const std::vector<T> &values)
: prefix_sum(values.begin(), values.end()) {}
int size() const { return int(prefix_.size()) - 1; }
T sum(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
return prefix_[right] - prefix_[left];
}
};
} // namespace noya
#endif // NOYA_PREFIX_SUM_HPP
#include <cassert>
#include <iterator>
#include <vector>
/// @complexity Time: O(n) construction and O(1) per range-sum query.
/// Space: O(n).
namespace noya {
/// @brief Static half-open range sums over an additive group.
/// Construction stores cumulative sums with an explicit zero at position zero.
/// The sum on [left,right) is the difference of the two boundary prefixes, so
/// each query needs no tree traversal and preserves the value type exactly.
template <class T> class prefix_sum {
std::vector<T> prefix_ = {T{}};
public:
prefix_sum() = default;
template <class Iterator> prefix_sum(Iterator first, Iterator last) {
for (; first != last; ++first) {
prefix_.push_back(prefix_.back() + *first);
}
}
explicit prefix_sum(const std::vector<T> &values)
: prefix_sum(values.begin(), values.end()) {}
int size() const { return int(prefix_.size()) - 1; }
T sum(int left, int right) const {
assert(0 <= left && left <= right && right <= size());
return prefix_[right] - prefix_[left];
}
};
} // namespace noya