sparse_segtree.hpp¶
Sparse segment tree for an enormous mostly-identity array. Each node stores one explicitly assigned position and the monoid product of its binary-search-tree subtree; interval midpoints keep the height bounded by the coordinate bit width while requiring only one node per touched point.
Verified by point_set_range_composite_large_array.
在巨大坐标域上动态开点，维护单点修改和区间聚合；适合无法按完整值域建树的在线问题。
Implementation¶
#ifndef NOYA_SPARSE_SEGTREE_HPP
#define NOYA_SPARSE_SEGTREE_HPP 1
/// @complexity Time: O(log coordinate_range) per point update or range
/// product. Space: O(number of distinct updated positions).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sparse segment tree for an enormous mostly-identity array. Each
/// node stores one explicitly assigned position and the monoid product of its
/// binary-search-tree subtree; interval midpoints keep the height bounded by
/// the coordinate bit width while requiring only one node per touched point.
template <class Monoid, class Coordinate = std::int64_t>
class sparse_segtree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
Coordinate position;
int left = -1;
int right = -1;
value_type value;
value_type product;
};
Coordinate left_bound_ = 0;
Coordinate right_bound_ = 0;
int root_ = -1;
std::vector<node> nodes_;
int new_node(Coordinate position, const value_type &value) {
nodes_.push_back({position, -1, -1, value, value});
return int(nodes_.size()) - 1;
}
void pull(int current) {
value_type product = nodes_[current].value;
if (nodes_[current].left != -1) {
product = Monoid::op(nodes_[nodes_[current].left].product, product);
}
if (nodes_[current].right != -1) {
product = Monoid::op(product, nodes_[nodes_[current].right].product);
}
nodes_[current].product = product;
}
int set_rec(int current, Coordinate low, Coordinate high,
Coordinate position, value_type value) {
if (current == -1) {
return new_node(position, value);
}
if (nodes_[current].position == position) {
nodes_[current].value = value;
pull(current);
return current;
}
Coordinate middle = low + (high - low) / 2;
if (position < middle) {
if (nodes_[current].position < position) {
std::swap(nodes_[current].position, position);
std::swap(nodes_[current].value, value);
}
nodes_[current].left = set_rec(nodes_[current].left, low, middle,
position, std::move(value));
} else {
if (position < nodes_[current].position) {
std::swap(nodes_[current].position, position);
std::swap(nodes_[current].value, value);
}
nodes_[current].right = set_rec(nodes_[current].right, middle, high,
position, std::move(value));
}
pull(current);
return current;
}
void prod_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, value_type &result) const {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right || current == -1) {
return;
}
if (left == low && right == high) {
result = Monoid::op(result, nodes_[current].product);
return;
}
Coordinate middle = low + (high - low) / 2;
prod_rec(nodes_[current].left, low, middle, left, right, result);
if (left <= nodes_[current].position &&
nodes_[current].position < right) {
result = Monoid::op(result, nodes_[current].value);
}
prod_rec(nodes_[current].right, middle, high, left, right, result);
}
public:
sparse_segtree() = default;
sparse_segtree(Coordinate left_bound, Coordinate right_bound,
std::size_t maximum_points = 0)
: left_bound_(left_bound), right_bound_(right_bound) {
assert(left_bound_ < right_bound_);
nodes_.reserve(maximum_points);
}
int stored_points() const { return int(nodes_.size()); }
void set(Coordinate position, const value_type &value) {
assert(left_bound_ <= position && position < right_bound_);
root_ = set_rec(root_, left_bound_, right_bound_, position, value);
}
value_type get(Coordinate position) const {
assert(left_bound_ <= position && position < right_bound_);
int current = root_;
while (current != -1) {
if (position == nodes_[current].position) {
return nodes_[current].value;
}
current = position < nodes_[current].position
? nodes_[current].left
: nodes_[current].right;
}
return Monoid::unit();
}
value_type prod(Coordinate left, Coordinate right) const {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
value_type result = Monoid::unit();
prod_rec(root_, left_bound_, right_bound_, left, right, result);
return result;
}
value_type all_prod() const {
return root_ == -1 ? Monoid::unit() : nodes_[root_].product;
}
};
} // namespace noya
#endif // NOYA_SPARSE_SEGTREE_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
/// @complexity Time: O(log coordinate_range) per point update or range
/// product. Space: O(number of distinct updated positions).
namespace noya {
/// @brief Sparse segment tree for an enormous mostly-identity array. Each
/// node stores one explicitly assigned position and the monoid product of its
/// binary-search-tree subtree; interval midpoints keep the height bounded by
/// the coordinate bit width while requiring only one node per touched point.
template <class Monoid, class Coordinate = std::int64_t>
class sparse_segtree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
Coordinate position;
int left = -1;
int right = -1;
value_type value;
value_type product;
};
Coordinate left_bound_ = 0;
Coordinate right_bound_ = 0;
int root_ = -1;
std::vector<node> nodes_;
int new_node(Coordinate position, const value_type &value) {
nodes_.push_back({position, -1, -1, value, value});
return int(nodes_.size()) - 1;
}
void pull(int current) {
value_type product = nodes_[current].value;
if (nodes_[current].left != -1) {
product = Monoid::op(nodes_[nodes_[current].left].product, product);
}
if (nodes_[current].right != -1) {
product = Monoid::op(product, nodes_[nodes_[current].right].product);
}
nodes_[current].product = product;
}
int set_rec(int current, Coordinate low, Coordinate high,
Coordinate position, value_type value) {
if (current == -1) {
return new_node(position, value);
}
if (nodes_[current].position == position) {
nodes_[current].value = value;
pull(current);
return current;
}
Coordinate middle = low + (high - low) / 2;
if (position < middle) {
if (nodes_[current].position < position) {
std::swap(nodes_[current].position, position);
std::swap(nodes_[current].value, value);
}
nodes_[current].left = set_rec(nodes_[current].left, low, middle,
position, std::move(value));
} else {
if (position < nodes_[current].position) {
std::swap(nodes_[current].position, position);
std::swap(nodes_[current].value, value);
}
nodes_[current].right = set_rec(nodes_[current].right, middle, high,
position, std::move(value));
}
pull(current);
return current;
}
void prod_rec(int current, Coordinate low, Coordinate high, Coordinate left,
Coordinate right, value_type &result) const {
left = std::max(left, low);
right = std::min(right, high);
if (left >= right || current == -1) {
return;
}
if (left == low && right == high) {
result = Monoid::op(result, nodes_[current].product);
return;
}
Coordinate middle = low + (high - low) / 2;
prod_rec(nodes_[current].left, low, middle, left, right, result);
if (left <= nodes_[current].position &&
nodes_[current].position < right) {
result = Monoid::op(result, nodes_[current].value);
}
prod_rec(nodes_[current].right, middle, high, left, right, result);
}
public:
sparse_segtree() = default;
sparse_segtree(Coordinate left_bound, Coordinate right_bound,
std::size_t maximum_points = 0)
: left_bound_(left_bound), right_bound_(right_bound) {
assert(left_bound_ < right_bound_);
nodes_.reserve(maximum_points);
}
int stored_points() const { return int(nodes_.size()); }
void set(Coordinate position, const value_type &value) {
assert(left_bound_ <= position && position < right_bound_);
root_ = set_rec(root_, left_bound_, right_bound_, position, value);
}
value_type get(Coordinate position) const {
assert(left_bound_ <= position && position < right_bound_);
int current = root_;
while (current != -1) {
if (position == nodes_[current].position) {
return nodes_[current].value;
}
current = position < nodes_[current].position
? nodes_[current].left
: nodes_[current].right;
}
return Monoid::unit();
}
value_type prod(Coordinate left, Coordinate right) const {
assert(left_bound_ <= left && left <= right && right <= right_bound_);
value_type result = Monoid::unit();
prod_rec(root_, left_bound_, right_bound_, left, right, result);
return result;
}
value_type all_prod() const {
return root_ == -1 ? Monoid::unit() : nodes_[root_].product;
}
};
} // namespace noya