sparse_range_affine_sum.hpp¶
Dynamic lazy segment tree for an initially zero huge array. Missing nodes mean an all-zero interval; an affine tag transforms a segment sum by sum <- multiplier * sum + addition * length. Tags are composed in chronological order and queries carry inherited tags without materializing untouched children.
Verified by range_affine_range_sum_large_array.
在巨大下标域上维护区间仿射变换与区间和，只为访问过的节点分配内存。
Implementation¶
#ifndef NOYA_SPARSE_RANGE_AFFINE_SUM_HPP
#define NOYA_SPARSE_RANGE_AFFINE_SUM_HPP 1
/// @complexity Time: O(log coordinate_range) per range update or query.
/// Space: O(u log coordinate_range) after u updates.
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Dynamic lazy segment tree for an initially zero huge array. Missing
/// nodes mean an all-zero interval; an affine tag transforms a segment sum by
/// `sum <- multiplier * sum + addition * length`. Tags are composed in
/// chronological order and queries carry inherited tags without materializing
/// untouched children.
template <class T, class Coordinate = std::int64_t>
class sparse_range_affine_sum {
struct node {
int left = -1;
int right = -1;
T sum = 0;
T multiplier = 1;
T addition = 0;
};
Coordinate left_bound_ = 0;
Coordinate right_bound_ = 0;
std::vector<node> nodes_;
int new_node() {
nodes_.push_back({});
return int(nodes_.size()) - 1;
}
void apply_to(int current, Coordinate length, const T &multiplier,
const T &addition) {
node &target = nodes_[current];
target.sum = multiplier * target.sum + addition * T(length);
target.multiplier = multiplier * target.multiplier;
target.addition = multiplier * target.addition + addition;
}
void push(int current, Coordinate low, Coordinate high) {
if (high - low == 1) {
return;
}
if (nodes_[current].multiplier == T(1) &&
nodes_[current].addition == T(0)) {
return;
}
Coordinate middle = low + (high - low) / 2;
if (nodes_[current].left == -1) {
int child = new_node();
nodes_[current].left = child;
}
if (nodes_[current].right == -1) {
int child = new_node();
nodes_[current].right = child;
}
T multiplier = nodes_[current].multiplier;
T addition = nodes_[current].addition;
int left = nodes_[current].left;
int right = nodes_[current].right;
apply_to(left, middle - low, multiplier, addition);
apply_to(right, high - middle, multiplier, addition);
nodes_[current].multiplier = T(1);
nodes_[current].addition = T(0);
}
T node_sum(int current) const {
return current == -1 ? T(0) : nodes_[current].sum;
}
int apply_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, const T &multiplier, const T &addition) {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right) {
return current;
}
if (current == -1) {
current = new_node();
}
if (left == low && right == high) {
apply_to(current, high - low, multiplier, addition);
return current;
}
push(current, low, high);
Coordinate middle = low + (high - low) / 2;
int left_child = nodes_[current].left;
int right_child = nodes_[current].right;
left_child = apply_rec(left_child, low, middle, left, right, multiplier,
addition);
right_child = apply_rec(right_child, middle, high, left, right, multiplier,
addition);
nodes_[current].left = left_child;
nodes_[current].right = right_child;
nodes_[current].sum = node_sum(left_child) + node_sum(right_child);
return current;
}
T prod_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, T inherited_multiplier,
T inherited_addition) const {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right) {
return T(0);
}
if (current == -1) {
return inherited_addition * T(right - left);
}
const node &target = nodes_[current];
if (left == low && right == high) {
return inherited_multiplier * target.sum +
inherited_addition * T(high - low);
}
inherited_addition =
inherited_multiplier * target.addition + inherited_addition;
inherited_multiplier *= target.multiplier;
Coordinate middle = low + (high - low) / 2;
return prod_rec(target.left, low, middle, left, right,
inherited_multiplier, inherited_addition) +
prod_rec(target.right, middle, high, left, right,
inherited_multiplier, inherited_addition);
}
public:
sparse_range_affine_sum() = default;
sparse_range_affine_sum(Coordinate left_bound, Coordinate right_bound,
std::size_t maximum_nodes = 0)
: left_bound_(left_bound), right_bound_(right_bound) {
assert(left_bound_ < right_bound_);
nodes_.reserve(maximum_nodes);
new_node();
}
int nodes() const { return int(nodes_.size()); }
void apply(Coordinate left, Coordinate right, const T &multiplier,
const T &addition) {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
apply_rec(0, left_bound_, right_bound_, left, right, multiplier, addition);
}
T prod(Coordinate left, Coordinate right) const {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
return prod_rec(0, left_bound_, right_bound_, left, right, T(1), T(0));
}
T all_prod() const { return nodes_[0].sum; }
};
} // namespace noya
#endif // NOYA_SPARSE_RANGE_AFFINE_SUM_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <vector>
/// @complexity Time: O(log coordinate_range) per range update or query.
/// Space: O(u log coordinate_range) after u updates.
namespace noya {
/// @brief Dynamic lazy segment tree for an initially zero huge array. Missing
/// nodes mean an all-zero interval; an affine tag transforms a segment sum by
/// `sum <- multiplier * sum + addition * length`. Tags are composed in
/// chronological order and queries carry inherited tags without materializing
/// untouched children.
template <class T, class Coordinate = std::int64_t>
class sparse_range_affine_sum {
struct node {
int left = -1;
int right = -1;
T sum = 0;
T multiplier = 1;
T addition = 0;
};
Coordinate left_bound_ = 0;
Coordinate right_bound_ = 0;
std::vector<node> nodes_;
int new_node() {
nodes_.push_back({});
return int(nodes_.size()) - 1;
}
void apply_to(int current, Coordinate length, const T &multiplier,
const T &addition) {
node &target = nodes_[current];
target.sum = multiplier * target.sum + addition * T(length);
target.multiplier = multiplier * target.multiplier;
target.addition = multiplier * target.addition + addition;
}
void push(int current, Coordinate low, Coordinate high) {
if (high - low == 1) {
return;
}
if (nodes_[current].multiplier == T(1) &&
nodes_[current].addition == T(0)) {
return;
}
Coordinate middle = low + (high - low) / 2;
if (nodes_[current].left == -1) {
int child = new_node();
nodes_[current].left = child;
}
if (nodes_[current].right == -1) {
int child = new_node();
nodes_[current].right = child;
}
T multiplier = nodes_[current].multiplier;
T addition = nodes_[current].addition;
int left = nodes_[current].left;
int right = nodes_[current].right;
apply_to(left, middle - low, multiplier, addition);
apply_to(right, high - middle, multiplier, addition);
nodes_[current].multiplier = T(1);
nodes_[current].addition = T(0);
}
T node_sum(int current) const {
return current == -1 ? T(0) : nodes_[current].sum;
}
int apply_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, const T &multiplier, const T &addition) {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right) {
return current;
}
if (current == -1) {
current = new_node();
}
if (left == low && right == high) {
apply_to(current, high - low, multiplier, addition);
return current;
}
push(current, low, high);
Coordinate middle = low + (high - low) / 2;
int left_child = nodes_[current].left;
int right_child = nodes_[current].right;
left_child = apply_rec(left_child, low, middle, left, right, multiplier,
addition);
right_child = apply_rec(right_child, middle, high, left, right, multiplier,
addition);
nodes_[current].left = left_child;
nodes_[current].right = right_child;
nodes_[current].sum = node_sum(left_child) + node_sum(right_child);
return current;
}
T prod_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, T inherited_multiplier,
T inherited_addition) const {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right) {
return T(0);
}
if (current == -1) {
return inherited_addition * T(right - left);
}
const node &target = nodes_[current];
if (left == low && right == high) {
return inherited_multiplier * target.sum +
inherited_addition * T(high - low);
}
inherited_addition =
inherited_multiplier * target.addition + inherited_addition;
inherited_multiplier *= target.multiplier;
Coordinate middle = low + (high - low) / 2;
return prod_rec(target.left, low, middle, left, right,
inherited_multiplier, inherited_addition) +
prod_rec(target.right, middle, high, left, right,
inherited_multiplier, inherited_addition);
}
public:
sparse_range_affine_sum() = default;
sparse_range_affine_sum(Coordinate left_bound, Coordinate right_bound,
std::size_t maximum_nodes = 0)
: left_bound_(left_bound), right_bound_(right_bound) {
assert(left_bound_ < right_bound_);
nodes_.reserve(maximum_nodes);
new_node();
}
int nodes() const { return int(nodes_.size()); }
void apply(Coordinate left, Coordinate right, const T &multiplier,
const T &addition) {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
apply_rec(0, left_bound_, right_bound_, left, right, multiplier, addition);
}
T prod(Coordinate left, Coordinate right) const {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
return prod_rec(0, left_bound_, right_bound_, left, right, T(1), T(0));
}
T all_prod() const { return nodes_[0].sum; }
};
} // namespace noya