prefix_sum.hpp¶
预处理一维前缀和，以常数时间回答静态区间和；适合数组不再修改、但区间求和很多的题目。
Complexity: Time: O(n) construction and O(1) per range-sum query. Space: O(n).
AC 记录：static_range_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 [l,r) 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> s = {T{}};
public:
prefix_sum() = default;
template <class Iterator> prefix_sum(Iterator a, Iterator lst) {
for (; a != lst; ++a) {
s.push_back(s.back() + *a);
}
}
explicit prefix_sum(const std::vector<T> &arr)
: prefix_sum(arr.begin(), arr.end()) {}
int size() const { return int(s.size()) - 1; }
T sum(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
return s[r] - s[l];
}
};
} // namespace noya
#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 [l,r) 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> s = {T{}};
public:
prefix_sum() = default;
template <class Iterator> prefix_sum(Iterator a, Iterator lst) {
for (; a != lst; ++a) {
s.push_back(s.back() + *a);
}
}
explicit prefix_sum(const std::vector<T> &arr)
: prefix_sum(arr.begin(), arr.end()) {}
int size() const { return int(s.size()) - 1; }
T sum(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
return s[r] - s[l];
}
};
} // 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 [l,r) 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> s = {T{}};
public:
prefix_sum() = default;
template <class Iterator> prefix_sum(Iterator a, Iterator lst) {
for (; a != lst; ++a) {
s.push_back(s.back() + *a);
}
}
explicit prefix_sum(const std::vector<T> &arr)
: prefix_sum(arr.begin(), arr.end()) {}
int size() const { return int(s.size()) - 1; }
T sum(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
return s[r] - s[l];
}
};
} // namespace noya