lazy_segtree.hpp¶
Lazy segment tree for a monoid acted on by a mapping monoid. Monoid provides value_type, unit(), and op(left, right). Action provides value_type, unit(), composition(newer, older), and apply(action, monoid_value).
Verified by range_affine_point_get, range_affine_range_sum.
维护区间作用、区间聚合以及懒标记下传；题目同时出现区间修改和区间查询时使用。
Implementation¶
#ifndef NOYA_LAZY_SEGTREE_HPP
#define NOYA_LAZY_SEGTREE_HPP 1
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
#include <cassert>
#include <vector>
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(left, right)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(action, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int size = 1;
int log = 0;
std::vector<S> data;
std::vector<F> lazy;
lazy_segtree() = default;
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &values) { build(values); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &values) {
n = int(values.size());
size = 1;
log = 0;
while (size < n) {
size <<= 1;
log++;
}
data.assign(size << 1, Monoid::unit());
lazy.assign(size, Action::unit());
for (int i = 0; i < n; i++) {
data[size + i] = values[i];
}
for (int node = size - 1; node >= 1; node--) {
pull(node);
}
}
void set(int position, const S &value) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
data[position] = value;
for (int height = 1; height <= log; height++) {
pull(position >> height);
}
}
S get(int position) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
return data[position];
}
S prod(int left, int right) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return Monoid::unit();
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
S first = Monoid::unit();
S second = Monoid::unit();
while (left < right) {
if (left & 1) {
first = Monoid::op(first, data[left++]);
}
if (right & 1) {
second = Monoid::op(data[--right], second);
}
left >>= 1;
right >>= 1;
}
return Monoid::op(first, second);
}
S all_prod() const { return data[1]; }
/// @brief Apply an action to every element in [left, right).
void apply(int left, int right, const F &action) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return;
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
int original_left = left;
int original_right = right;
while (left < right) {
if (left & 1) {
all_apply(left++, action);
}
if (right & 1) {
all_apply(--right, action);
}
left >>= 1;
right >>= 1;
}
left = original_left;
right = original_right;
for (int height = 1; height <= log; height++) {
if (((left >> height) << height) != left) {
pull(left >> height);
}
if (((right >> height) << height) != right) {
pull((right - 1) >> height);
}
}
}
private:
void pull(int node) {
data[node] = Monoid::op(data[node << 1], data[node << 1 | 1]);
}
void all_apply(int node, const F &action) {
data[node] = Action::apply(action, data[node]);
if (node < size) {
lazy[node] = Action::composition(action, lazy[node]);
}
}
void push(int node) {
all_apply(node << 1, lazy[node]);
all_apply(node << 1 | 1, lazy[node]);
lazy[node] = Action::unit();
}
};
} // namespace noya
#endif // NOYA_LAZY_SEGTREE_HPP
#include <cassert>
#include <vector>
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(left, right)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(action, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int size = 1;
int log = 0;
std::vector<S> data;
std::vector<F> lazy;
lazy_segtree() = default;
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &values) { build(values); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &values) {
n = int(values.size());
size = 1;
log = 0;
while (size < n) {
size <<= 1;
log++;
}
data.assign(size << 1, Monoid::unit());
lazy.assign(size, Action::unit());
for (int i = 0; i < n; i++) {
data[size + i] = values[i];
}
for (int node = size - 1; node >= 1; node--) {
pull(node);
}
}
void set(int position, const S &value) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
data[position] = value;
for (int height = 1; height <= log; height++) {
pull(position >> height);
}
}
S get(int position) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
return data[position];
}
S prod(int left, int right) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return Monoid::unit();
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
S first = Monoid::unit();
S second = Monoid::unit();
while (left < right) {
if (left & 1) {
first = Monoid::op(first, data[left++]);
}
if (right & 1) {
second = Monoid::op(data[--right], second);
}
left >>= 1;
right >>= 1;
}
return Monoid::op(first, second);
}
S all_prod() const { return data[1]; }
/// @brief Apply an action to every element in [left, right).
void apply(int left, int right, const F &action) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return;
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
int original_left = left;
int original_right = right;
while (left < right) {
if (left & 1) {
all_apply(left++, action);
}
if (right & 1) {
all_apply(--right, action);
}
left >>= 1;
right >>= 1;
}
left = original_left;
right = original_right;
for (int height = 1; height <= log; height++) {
if (((left >> height) << height) != left) {
pull(left >> height);
}
if (((right >> height) << height) != right) {
pull((right - 1) >> height);
}
}
}
private:
void pull(int node) {
data[node] = Monoid::op(data[node << 1], data[node << 1 | 1]);
}
void all_apply(int node, const F &action) {
data[node] = Action::apply(action, data[node]);
if (node < size) {
lazy[node] = Action::composition(action, lazy[node]);
}
}
void push(int node) {
all_apply(node << 1, lazy[node]);
all_apply(node << 1 | 1, lazy[node]);
lazy[node] = Action::unit();
}
};
} // namespace noya