sparse_segtree.hpp¶
在巨大坐标域上动态开点，维护单点修改和区间聚合；适合无法按完整值域建树的在线问题。
Complexity: Time: O(log coordinate_range) per point update or range product. Space: O(u), where u is the number of distinct assigned positions.
AC 记录：point_set_range_composite_large_array。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log coordinate_range) per point update or range
/// product. Space: O(u), where u is the number of distinct assigned 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.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class Monoid, class Coordinate = std::int64_t> class sparse_segtree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
Coordinate pos;
int ls = -1;
int rs = -1;
value_type val;
value_type prd;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
int rt = -1;
std::vector<node> tr;
// Integer average rounded down without overflowing either endpoint.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
int new_node(Coordinate pos, const value_type &val) {
tr.push_back({pos, -1, -1, val, val});
return int(tr.size()) - 1;
}
void pull(int cur) {
value_type prd = tr[cur].val;
if (tr[cur].ls != -1) {
prd = Monoid::op(tr[tr[cur].ls].prd, prd);
}
if (tr[cur].rs != -1) {
prd = Monoid::op(prd, tr[tr[cur].rs].prd);
}
tr[cur].prd = prd;
}
int set_rec(int cur, Coordinate low, Coordinate big, Coordinate pos,
value_type val) {
if (cur == -1) {
return new_node(pos, val);
}
if (tr[cur].pos == pos) {
tr[cur].val = val;
pull(cur);
return cur;
}
Coordinate mid = midpoint(low, big);
if (pos < mid) {
if (tr[cur].pos < pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].ls = set_rec(tr[cur].ls, low, mid, pos, std::move(val));
} else {
if (pos < tr[cur].pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].rs = set_rec(tr[cur].rs, mid, big, pos, std::move(val));
}
pull(cur);
return cur;
}
void prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, value_type &res) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r || cur == -1) {
return;
}
if (l == low && r == big) {
res = Monoid::op(res, tr[cur].prd);
return;
}
Coordinate mid = midpoint(low, big);
prod_rec(tr[cur].ls, low, mid, l, r, res);
if (l <= tr[cur].pos && tr[cur].pos < r) {
res = Monoid::op(res, tr[cur].val);
}
prod_rec(tr[cur].rs, mid, big, l, r, res);
}
public:
sparse_segtree() = default;
sparse_segtree(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
}
int stored_points() const { return int(tr.size()); }
void set(Coordinate pos, const value_type &val) {
assert(lo_ <= pos && pos < hi_);
rt = set_rec(rt, lo_, hi_, pos, val);
}
value_type get(Coordinate pos) const {
assert(lo_ <= pos && pos < hi_);
int cur = rt;
while (cur != -1) {
if (pos == tr[cur].pos) {
return tr[cur].val;
}
cur = pos < tr[cur].pos ? tr[cur].ls : tr[cur].rs;
}
return Monoid::unit();
}
value_type prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
value_type res = Monoid::unit();
prod_rec(rt, lo_, hi_, l, r, res);
return res;
}
value_type all_prod() const { return rt == -1 ? Monoid::unit() : tr[rt].prd; }
};
} // namespace noya
#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(u), where u is the number of distinct assigned 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.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class Monoid, class Coordinate = std::int64_t> class sparse_segtree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
Coordinate pos;
int ls = -1;
int rs = -1;
value_type val;
value_type prd;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
int rt = -1;
std::vector<node> tr;
// Integer average rounded down without overflowing either endpoint.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
int new_node(Coordinate pos, const value_type &val) {
tr.push_back({pos, -1, -1, val, val});
return int(tr.size()) - 1;
}
void pull(int cur) {
value_type prd = tr[cur].val;
if (tr[cur].ls != -1) {
prd = Monoid::op(tr[tr[cur].ls].prd, prd);
}
if (tr[cur].rs != -1) {
prd = Monoid::op(prd, tr[tr[cur].rs].prd);
}
tr[cur].prd = prd;
}
int set_rec(int cur, Coordinate low, Coordinate big, Coordinate pos,
value_type val) {
if (cur == -1) {
return new_node(pos, val);
}
if (tr[cur].pos == pos) {
tr[cur].val = val;
pull(cur);
return cur;
}
Coordinate mid = midpoint(low, big);
if (pos < mid) {
if (tr[cur].pos < pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].ls = set_rec(tr[cur].ls, low, mid, pos, std::move(val));
} else {
if (pos < tr[cur].pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].rs = set_rec(tr[cur].rs, mid, big, pos, std::move(val));
}
pull(cur);
return cur;
}
void prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, value_type &res) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r || cur == -1) {
return;
}
if (l == low && r == big) {
res = Monoid::op(res, tr[cur].prd);
return;
}
Coordinate mid = midpoint(low, big);
prod_rec(tr[cur].ls, low, mid, l, r, res);
if (l <= tr[cur].pos && tr[cur].pos < r) {
res = Monoid::op(res, tr[cur].val);
}
prod_rec(tr[cur].rs, mid, big, l, r, res);
}
public:
sparse_segtree() = default;
sparse_segtree(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
}
int stored_points() const { return int(tr.size()); }
void set(Coordinate pos, const value_type &val) {
assert(lo_ <= pos && pos < hi_);
rt = set_rec(rt, lo_, hi_, pos, val);
}
value_type get(Coordinate pos) const {
assert(lo_ <= pos && pos < hi_);
int cur = rt;
while (cur != -1) {
if (pos == tr[cur].pos) {
return tr[cur].val;
}
cur = pos < tr[cur].pos ? tr[cur].ls : tr[cur].rs;
}
return Monoid::unit();
}
value_type prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
value_type res = Monoid::unit();
prod_rec(rt, lo_, hi_, l, r, res);
return res;
}
value_type all_prod() const { return rt == -1 ? Monoid::unit() : tr[rt].prd; }
};
} // 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(u), where u is the number of distinct assigned 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.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class Monoid, class Coordinate = std::int64_t> class sparse_segtree {
public:
using value_type = typename Monoid::value_type;
private:
struct node {
Coordinate pos;
int ls = -1;
int rs = -1;
value_type val;
value_type prd;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
int rt = -1;
std::vector<node> tr;
// Integer average rounded down without overflowing either endpoint.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
int new_node(Coordinate pos, const value_type &val) {
tr.push_back({pos, -1, -1, val, val});
return int(tr.size()) - 1;
}
void pull(int cur) {
value_type prd = tr[cur].val;
if (tr[cur].ls != -1) {
prd = Monoid::op(tr[tr[cur].ls].prd, prd);
}
if (tr[cur].rs != -1) {
prd = Monoid::op(prd, tr[tr[cur].rs].prd);
}
tr[cur].prd = prd;
}
int set_rec(int cur, Coordinate low, Coordinate big, Coordinate pos,
value_type val) {
if (cur == -1) {
return new_node(pos, val);
}
if (tr[cur].pos == pos) {
tr[cur].val = val;
pull(cur);
return cur;
}
Coordinate mid = midpoint(low, big);
if (pos < mid) {
if (tr[cur].pos < pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].ls = set_rec(tr[cur].ls, low, mid, pos, std::move(val));
} else {
if (pos < tr[cur].pos) {
std::swap(tr[cur].pos, pos);
std::swap(tr[cur].val, val);
}
tr[cur].rs = set_rec(tr[cur].rs, mid, big, pos, std::move(val));
}
pull(cur);
return cur;
}
void prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, value_type &res) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r || cur == -1) {
return;
}
if (l == low && r == big) {
res = Monoid::op(res, tr[cur].prd);
return;
}
Coordinate mid = midpoint(low, big);
prod_rec(tr[cur].ls, low, mid, l, r, res);
if (l <= tr[cur].pos && tr[cur].pos < r) {
res = Monoid::op(res, tr[cur].val);
}
prod_rec(tr[cur].rs, mid, big, l, r, res);
}
public:
sparse_segtree() = default;
sparse_segtree(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
}
int stored_points() const { return int(tr.size()); }
void set(Coordinate pos, const value_type &val) {
assert(lo_ <= pos && pos < hi_);
rt = set_rec(rt, lo_, hi_, pos, val);
}
value_type get(Coordinate pos) const {
assert(lo_ <= pos && pos < hi_);
int cur = rt;
while (cur != -1) {
if (pos == tr[cur].pos) {
return tr[cur].val;
}
cur = pos < tr[cur].pos ? tr[cur].ls : tr[cur].rs;
}
return Monoid::unit();
}
value_type prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
value_type res = Monoid::unit();
prod_rec(rt, lo_, hi_, l, r, res);
return res;
}
value_type all_prod() const { return rt == -1 ? Monoid::unit() : tr[rt].prd; }
};
} // namespace noya