sparse_range_affine_sum.hpp¶
在巨大下标域上维护区间仿射变换与区间和，只为访问过的节点分配内存。
Complexity: Time: O(log coordinate_range) per range update or query. Space: O(u log coordinate_range) after u updates.
AC 记录：range_affine_range_sum_large_array。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 <type_traits>
#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 <- mul * sum + add * len`. Tags are composed in
/// chronological order and queries carry inherited tags without materializing
/// untouched children.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class T, class Coordinate = std::int64_t>
class sparse_range_affine_sum {
using U = std::conditional_t<(sizeof(Coordinate) > sizeof(std::uint64_t)),
unsigned __int128, std::uint64_t>;
struct node {
int ls = -1;
int rs = -1;
T sum = 0;
T mul = 1;
T add = 0;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
std::vector<node> tr;
int new_node() {
tr.push_back({});
return int(tr.size()) - 1;
}
static U span(Coordinate l, Coordinate r) { return U(r) - U(l); }
// Integer average rounded down, including GCC's extended integer types.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
void apply_to(int cur, U len, const T &mul, const T &add) {
node &tar = tr[cur];
tar.sum = mul * tar.sum + add * T(len);
tar.mul = mul * tar.mul;
tar.add = mul * tar.add + add;
}
void push(int cur, Coordinate low, Coordinate big) {
if (span(low, big) == 1) {
return;
}
if (tr[cur].mul == T(1) && tr[cur].add == T(0)) {
return;
}
Coordinate mid = midpoint(low, big);
if (tr[cur].ls == -1) {
int ch = new_node();
tr[cur].ls = ch;
}
if (tr[cur].rs == -1) {
int ch = new_node();
tr[cur].rs = ch;
}
T mul = tr[cur].mul;
T add = tr[cur].add;
int l = tr[cur].ls;
int r = tr[cur].rs;
apply_to(l, span(low, mid), mul, add);
apply_to(r, span(mid, big), mul, add);
tr[cur].mul = T(1);
tr[cur].add = T(0);
}
T node_sum(int cur) const { return cur == -1 ? T(0) : tr[cur].sum; }
int apply_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, const T &mul, const T &add) {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return cur;
}
if (cur == -1) {
cur = new_node();
}
if (l == low && r == big) {
apply_to(cur, span(low, big), mul, add);
return cur;
}
push(cur, low, big);
Coordinate mid = midpoint(low, big);
int lc = tr[cur].ls;
int rc = tr[cur].rs;
lc = apply_rec(lc, low, mid, l, r, mul, add);
rc = apply_rec(rc, mid, big, l, r, mul, add);
tr[cur].ls = lc;
tr[cur].rs = rc;
tr[cur].sum = node_sum(lc) + node_sum(rc);
return cur;
}
T prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, T am, T aa) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return T(0);
}
if (cur == -1) {
return aa * T(span(l, r));
}
const node &tar = tr[cur];
if (l == low && r == big) {
return am * tar.sum + aa * T(span(low, big));
}
aa = am * tar.add + aa;
am *= tar.mul;
Coordinate mid = midpoint(low, big);
return prod_rec(tar.ls, low, mid, l, r, am, aa) +
prod_rec(tar.rs, mid, big, l, r, am, aa);
}
public:
sparse_range_affine_sum() = default;
sparse_range_affine_sum(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
new_node();
}
int nodes() const { return int(tr.size()); }
void apply(Coordinate l, Coordinate r, const T &mul, const T &add) {
assert(lo_ <= l && l <= r && r <= hi_);
apply_rec(0, lo_, hi_, l, r, mul, add);
}
T prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
return prod_rec(0, lo_, hi_, l, r, T(1), T(0));
}
T all_prod() const { return tr.empty() ? T(0) : tr[0].sum; }
};
} // namespace noya
#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 <type_traits>
#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 <- mul * sum + add * len`. Tags are composed in
/// chronological order and queries carry inherited tags without materializing
/// untouched children.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class T, class Coordinate = std::int64_t>
class sparse_range_affine_sum {
using U = std::conditional_t<(sizeof(Coordinate) > sizeof(std::uint64_t)),
unsigned __int128, std::uint64_t>;
struct node {
int ls = -1;
int rs = -1;
T sum = 0;
T mul = 1;
T add = 0;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
std::vector<node> tr;
int new_node() {
tr.push_back({});
return int(tr.size()) - 1;
}
static U span(Coordinate l, Coordinate r) { return U(r) - U(l); }
// Integer average rounded down, including GCC's extended integer types.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
void apply_to(int cur, U len, const T &mul, const T &add) {
node &tar = tr[cur];
tar.sum = mul * tar.sum + add * T(len);
tar.mul = mul * tar.mul;
tar.add = mul * tar.add + add;
}
void push(int cur, Coordinate low, Coordinate big) {
if (span(low, big) == 1) {
return;
}
if (tr[cur].mul == T(1) && tr[cur].add == T(0)) {
return;
}
Coordinate mid = midpoint(low, big);
if (tr[cur].ls == -1) {
int ch = new_node();
tr[cur].ls = ch;
}
if (tr[cur].rs == -1) {
int ch = new_node();
tr[cur].rs = ch;
}
T mul = tr[cur].mul;
T add = tr[cur].add;
int l = tr[cur].ls;
int r = tr[cur].rs;
apply_to(l, span(low, mid), mul, add);
apply_to(r, span(mid, big), mul, add);
tr[cur].mul = T(1);
tr[cur].add = T(0);
}
T node_sum(int cur) const { return cur == -1 ? T(0) : tr[cur].sum; }
int apply_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, const T &mul, const T &add) {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return cur;
}
if (cur == -1) {
cur = new_node();
}
if (l == low && r == big) {
apply_to(cur, span(low, big), mul, add);
return cur;
}
push(cur, low, big);
Coordinate mid = midpoint(low, big);
int lc = tr[cur].ls;
int rc = tr[cur].rs;
lc = apply_rec(lc, low, mid, l, r, mul, add);
rc = apply_rec(rc, mid, big, l, r, mul, add);
tr[cur].ls = lc;
tr[cur].rs = rc;
tr[cur].sum = node_sum(lc) + node_sum(rc);
return cur;
}
T prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, T am, T aa) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return T(0);
}
if (cur == -1) {
return aa * T(span(l, r));
}
const node &tar = tr[cur];
if (l == low && r == big) {
return am * tar.sum + aa * T(span(low, big));
}
aa = am * tar.add + aa;
am *= tar.mul;
Coordinate mid = midpoint(low, big);
return prod_rec(tar.ls, low, mid, l, r, am, aa) +
prod_rec(tar.rs, mid, big, l, r, am, aa);
}
public:
sparse_range_affine_sum() = default;
sparse_range_affine_sum(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
new_node();
}
int nodes() const { return int(tr.size()); }
void apply(Coordinate l, Coordinate r, const T &mul, const T &add) {
assert(lo_ <= l && l <= r && r <= hi_);
apply_rec(0, lo_, hi_, l, r, mul, add);
}
T prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
return prod_rec(0, lo_, hi_, l, r, T(1), T(0));
}
T all_prod() const { return tr.empty() ? T(0) : tr[0].sum; }
};
} // namespace noya
#endif // NOYA_SPARSE_RANGE_AFFINE_SUM_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <type_traits>
#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 <- mul * sum + add * len`. Tags are composed in
/// chronological order and queries carry inherited tags without materializing
/// untouched children.
/// Coordinates are integers in the half-open domain [lo, hi).
template <class T, class Coordinate = std::int64_t>
class sparse_range_affine_sum {
using U = std::conditional_t<(sizeof(Coordinate) > sizeof(std::uint64_t)),
unsigned __int128, std::uint64_t>;
struct node {
int ls = -1;
int rs = -1;
T sum = 0;
T mul = 1;
T add = 0;
};
Coordinate lo_ = 0;
Coordinate hi_ = 0;
std::vector<node> tr;
int new_node() {
tr.push_back({});
return int(tr.size()) - 1;
}
static U span(Coordinate l, Coordinate r) { return U(r) - U(l); }
// Integer average rounded down, including GCC's extended integer types.
static Coordinate midpoint(Coordinate l, Coordinate r) {
return (l & r) + ((l ^ r) >> 1);
}
void apply_to(int cur, U len, const T &mul, const T &add) {
node &tar = tr[cur];
tar.sum = mul * tar.sum + add * T(len);
tar.mul = mul * tar.mul;
tar.add = mul * tar.add + add;
}
void push(int cur, Coordinate low, Coordinate big) {
if (span(low, big) == 1) {
return;
}
if (tr[cur].mul == T(1) && tr[cur].add == T(0)) {
return;
}
Coordinate mid = midpoint(low, big);
if (tr[cur].ls == -1) {
int ch = new_node();
tr[cur].ls = ch;
}
if (tr[cur].rs == -1) {
int ch = new_node();
tr[cur].rs = ch;
}
T mul = tr[cur].mul;
T add = tr[cur].add;
int l = tr[cur].ls;
int r = tr[cur].rs;
apply_to(l, span(low, mid), mul, add);
apply_to(r, span(mid, big), mul, add);
tr[cur].mul = T(1);
tr[cur].add = T(0);
}
T node_sum(int cur) const { return cur == -1 ? T(0) : tr[cur].sum; }
int apply_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, const T &mul, const T &add) {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return cur;
}
if (cur == -1) {
cur = new_node();
}
if (l == low && r == big) {
apply_to(cur, span(low, big), mul, add);
return cur;
}
push(cur, low, big);
Coordinate mid = midpoint(low, big);
int lc = tr[cur].ls;
int rc = tr[cur].rs;
lc = apply_rec(lc, low, mid, l, r, mul, add);
rc = apply_rec(rc, mid, big, l, r, mul, add);
tr[cur].ls = lc;
tr[cur].rs = rc;
tr[cur].sum = node_sum(lc) + node_sum(rc);
return cur;
}
T prod_rec(int cur, Coordinate low, Coordinate big, Coordinate l,
Coordinate r, T am, T aa) const {
l = std::max(l, low);
r = std::min(r, big);
if (l >= r) {
return T(0);
}
if (cur == -1) {
return aa * T(span(l, r));
}
const node &tar = tr[cur];
if (l == low && r == big) {
return am * tar.sum + aa * T(span(low, big));
}
aa = am * tar.add + aa;
am *= tar.mul;
Coordinate mid = midpoint(low, big);
return prod_rec(tar.ls, low, mid, l, r, am, aa) +
prod_rec(tar.rs, mid, big, l, r, am, aa);
}
public:
sparse_range_affine_sum() = default;
sparse_range_affine_sum(Coordinate lo, Coordinate hi, std::size_t cap = 0)
: lo_(lo), hi_(hi) {
assert(lo_ < hi_);
tr.reserve(cap);
new_node();
}
int nodes() const { return int(tr.size()); }
void apply(Coordinate l, Coordinate r, const T &mul, const T &add) {
assert(lo_ <= l && l <= r && r <= hi_);
apply_rec(0, lo_, hi_, l, r, mul, add);
}
T prod(Coordinate l, Coordinate r) const {
assert(lo_ <= l && l <= r && r <= hi_);
return prod_rec(0, lo_, hi_, l, r, T(1), T(0));
}
T all_prod() const { return tr.empty() ? T(0) : tr[0].sum; }
};
} // namespace noya