persistent_affine_segtree.hpp¶
保留每次区间仿射修改后的线段树版本，并查询任一版本的区间和。
Complexity: Time: \(O(\log n)\) per range affine update, range copy, or query. Space: \(O(n + q \log n)\) nodes for \(q\) derived versions.
AC 记录：persistent_range_affine_range_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log n) per range affine update, range copy, or query.
/// Space: O(n + q log n) nodes for q derived versions.
#include <cassert>
#include <vector>
namespace noya {
/// @brief Persistent lazy segment tree for range affine transforms and sums.
/// Updates clone O(log n) nodes and share untouched subtrees. A range copy descends in a
/// destination version and a source version together, carrying source tags
/// without modifying source nodes. Destination tags are pushed only into fresh
/// clones, so every older root remains unchanged.
template <class T> class persistent_affine_segtree {
public:
persistent_affine_segtree() = default;
explicit persistent_affine_segtree(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(!a.empty());
n = int(a.size());
tr.clear();
tr.reserve(a.size() * 2);
rt0 = build_node(a, 0, n);
}
void reserve(int cap) { tr.reserve(cap); }
int initial_root() const { return rt0; }
int apply(int rt, int l, int r, T mul, T add) {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r || (mul == T(1) && add == T(0))) {
return rt;
}
return apply_node(rt, 0, n, l, r, mul, add);
}
int copy_range(int dr, int sr, int l, int r) {
assert(valid_root(dr) && valid_root(sr));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return dr;
}
return copy_node(dr, sr, 0, n, l, r, T(1), T(0));
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return T(0);
}
return prod_node(rt, 0, n, l, r, T(1), T(0));
}
private:
struct node {
T sum{};
T mul = T(1);
T add{};
int ls = -1;
int rs = -1;
};
int n = 0;
int rt0 = -1;
std::vector<node> tr;
bool valid_root(int rt) const { return 0 <= rt && rt < int(tr.size()); }
int make_node(const node &val) {
tr.push_back(val);
return int(tr.size()) - 1;
}
int clone_node(int id) { return make_node(tr[id]); }
int build_node(const std::vector<T> &a, int l, int r) {
if (r - l == 1) {
return make_node(node{.sum = a[l]});
}
int mid = l + (r - l) / 2;
int arr = build_node(a, l, mid);
int b = build_node(a, mid, r);
return make_node(node{.sum = tr[arr].sum + tr[b].sum, .ls = arr, .rs = b});
}
void apply_here(int id, int len, T mul, T add) {
tr[id].sum = mul * tr[id].sum + add * T(len);
tr[id].mul *= mul;
tr[id].add = mul * tr[id].add + add;
}
// Return whether both children were freshly cloned by this push.
bool push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return false;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return false;
}
int arr = clone_node(tr[id].ls);
int b = clone_node(tr[id].rs);
tr[id].ls = arr;
tr[id].rs = b;
apply_here(arr, ll, mul, add);
apply_here(b, lr, mul, add);
tr[id].mul = T(1);
tr[id].add = T(0);
return true;
}
void pull(int id) { tr[id].sum = tr[tr[id].ls].sum + tr[tr[id].rs].sum; }
int apply_node(int id, int l, int r, int ql, int qr, T mul, T add,
bool owned = false) {
if (qr <= l || r <= ql) {
return id;
}
int res = owned ? id : clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = l + (r - l) / 2;
bool fresh = push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add, fresh);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add, fresh);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr, T sm, T sa,
bool owned = false) {
if (qr <= l || r <= ql || (dst == src && sm == T(1) && sa == T(0))) {
return dst;
}
if (ql <= l && r <= qr) {
if (sm == T(1) && sa == T(0)) {
return src;
}
int res = clone_node(src);
apply_here(res, r - l, sm, sa);
return res;
}
int mid = l + (r - l) / 2;
int dc = owned ? dst : clone_node(dst);
bool fresh = push_cloned(dc, mid - l, r - mid);
T mul = sm * tr[src].mul;
T add = sm * tr[src].add + sa;
int arr = copy_node(tr[dc].ls, tr[src].ls, l, mid, ql, qr, mul, add, fresh);
int b = copy_node(tr[dc].rs, tr[src].rs, mid, r, ql, qr, mul, add, fresh);
tr[dc].ls = arr;
tr[dc].rs = b;
pull(dc);
return dc;
}
T prod_node(int id, int l, int r, int ql, int qr, T am, T aa) const {
if (qr <= l || r <= ql) {
return T(0);
}
if (ql <= l && r <= qr) {
return am * tr[id].sum + aa * T(r - l);
}
T mul = am * tr[id].mul;
T add = am * tr[id].add + aa;
int mid = l + (r - l) / 2;
if (qr <= mid) {
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add);
}
if (mid <= ql) {
return prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add) +
prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
};
} // namespace noya
// NOYA_PERSISTENT_AFFINE_SEGTREE_HPP
#ifndef NOYA_PERSISTENT_AFFINE_SEGTREE_HPP
#define NOYA_PERSISTENT_AFFINE_SEGTREE_HPP 1
/// @complexity Time: O(log n) per range affine update, range copy, or query.
/// Space: O(n + q log n) nodes for q derived versions.
#include <cassert>
#include <vector>
namespace noya {
/// @brief Persistent lazy segment tree for range affine transforms and sums.
/// Updates clone O(log n) nodes and share untouched subtrees. A range copy descends in a
/// destination version and a source version together, carrying source tags
/// without modifying source nodes. Destination tags are pushed only into fresh
/// clones, so every older root remains unchanged.
template <class T> class persistent_affine_segtree {
public:
persistent_affine_segtree() = default;
explicit persistent_affine_segtree(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(!a.empty());
n = int(a.size());
tr.clear();
tr.reserve(a.size() * 2);
rt0 = build_node(a, 0, n);
}
void reserve(int cap) { tr.reserve(cap); }
int initial_root() const { return rt0; }
int apply(int rt, int l, int r, T mul, T add) {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r || (mul == T(1) && add == T(0))) {
return rt;
}
return apply_node(rt, 0, n, l, r, mul, add);
}
int copy_range(int dr, int sr, int l, int r) {
assert(valid_root(dr) && valid_root(sr));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return dr;
}
return copy_node(dr, sr, 0, n, l, r, T(1), T(0));
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return T(0);
}
return prod_node(rt, 0, n, l, r, T(1), T(0));
}
private:
struct node {
T sum{};
T mul = T(1);
T add{};
int ls = -1;
int rs = -1;
};
int n = 0;
int rt0 = -1;
std::vector<node> tr;
bool valid_root(int rt) const { return 0 <= rt && rt < int(tr.size()); }
int make_node(const node &val) {
tr.push_back(val);
return int(tr.size()) - 1;
}
int clone_node(int id) { return make_node(tr[id]); }
int build_node(const std::vector<T> &a, int l, int r) {
if (r - l == 1) {
return make_node(node{.sum = a[l]});
}
int mid = l + (r - l) / 2;
int arr = build_node(a, l, mid);
int b = build_node(a, mid, r);
return make_node(node{.sum = tr[arr].sum + tr[b].sum, .ls = arr, .rs = b});
}
void apply_here(int id, int len, T mul, T add) {
tr[id].sum = mul * tr[id].sum + add * T(len);
tr[id].mul *= mul;
tr[id].add = mul * tr[id].add + add;
}
// Return whether both children were freshly cloned by this push.
bool push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return false;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return false;
}
int arr = clone_node(tr[id].ls);
int b = clone_node(tr[id].rs);
tr[id].ls = arr;
tr[id].rs = b;
apply_here(arr, ll, mul, add);
apply_here(b, lr, mul, add);
tr[id].mul = T(1);
tr[id].add = T(0);
return true;
}
void pull(int id) { tr[id].sum = tr[tr[id].ls].sum + tr[tr[id].rs].sum; }
int apply_node(int id, int l, int r, int ql, int qr, T mul, T add,
bool owned = false) {
if (qr <= l || r <= ql) {
return id;
}
int res = owned ? id : clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = l + (r - l) / 2;
bool fresh = push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add, fresh);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add, fresh);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr, T sm, T sa,
bool owned = false) {
if (qr <= l || r <= ql || (dst == src && sm == T(1) && sa == T(0))) {
return dst;
}
if (ql <= l && r <= qr) {
if (sm == T(1) && sa == T(0)) {
return src;
}
int res = clone_node(src);
apply_here(res, r - l, sm, sa);
return res;
}
int mid = l + (r - l) / 2;
int dc = owned ? dst : clone_node(dst);
bool fresh = push_cloned(dc, mid - l, r - mid);
T mul = sm * tr[src].mul;
T add = sm * tr[src].add + sa;
int arr = copy_node(tr[dc].ls, tr[src].ls, l, mid, ql, qr, mul, add, fresh);
int b = copy_node(tr[dc].rs, tr[src].rs, mid, r, ql, qr, mul, add, fresh);
tr[dc].ls = arr;
tr[dc].rs = b;
pull(dc);
return dc;
}
T prod_node(int id, int l, int r, int ql, int qr, T am, T aa) const {
if (qr <= l || r <= ql) {
return T(0);
}
if (ql <= l && r <= qr) {
return am * tr[id].sum + aa * T(r - l);
}
T mul = am * tr[id].mul;
T add = am * tr[id].add + aa;
int mid = l + (r - l) / 2;
if (qr <= mid) {
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add);
}
if (mid <= ql) {
return prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add) +
prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
};
} // namespace noya
#endif // NOYA_PERSISTENT_AFFINE_SEGTREE_HPP
/// @complexity Time: O(log n) per range affine update, range copy, or query.
/// Space: O(n + q log n) nodes for q derived versions.
#include <cassert>
#include <vector>
namespace noya {
/// @brief Persistent lazy segment tree for range affine transforms and sums.
/// Updates clone O(log n) nodes and share untouched subtrees. A range copy descends in a
/// destination version and a source version together, carrying source tags
/// without modifying source nodes. Destination tags are pushed only into fresh
/// clones, so every older root remains unchanged.
template <class T> class persistent_affine_segtree {
public:
persistent_affine_segtree() = default;
explicit persistent_affine_segtree(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(!a.empty());
n = int(a.size());
tr.clear();
tr.reserve(a.size() * 2);
rt0 = build_node(a, 0, n);
}
void reserve(int cap) { tr.reserve(cap); }
int initial_root() const { return rt0; }
int apply(int rt, int l, int r, T mul, T add) {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r || (mul == T(1) && add == T(0))) {
return rt;
}
return apply_node(rt, 0, n, l, r, mul, add);
}
int copy_range(int dr, int sr, int l, int r) {
assert(valid_root(dr) && valid_root(sr));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return dr;
}
return copy_node(dr, sr, 0, n, l, r, T(1), T(0));
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return T(0);
}
return prod_node(rt, 0, n, l, r, T(1), T(0));
}
private:
struct node {
T sum{};
T mul = T(1);
T add{};
int ls = -1;
int rs = -1;
};
int n = 0;
int rt0 = -1;
std::vector<node> tr;
bool valid_root(int rt) const { return 0 <= rt && rt < int(tr.size()); }
int make_node(const node &val) {
tr.push_back(val);
return int(tr.size()) - 1;
}
int clone_node(int id) { return make_node(tr[id]); }
int build_node(const std::vector<T> &a, int l, int r) {
if (r - l == 1) {
return make_node(node{.sum = a[l]});
}
int mid = l + (r - l) / 2;
int arr = build_node(a, l, mid);
int b = build_node(a, mid, r);
return make_node(node{.sum = tr[arr].sum + tr[b].sum, .ls = arr, .rs = b});
}
void apply_here(int id, int len, T mul, T add) {
tr[id].sum = mul * tr[id].sum + add * T(len);
tr[id].mul *= mul;
tr[id].add = mul * tr[id].add + add;
}
// Return whether both children were freshly cloned by this push.
bool push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return false;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return false;
}
int arr = clone_node(tr[id].ls);
int b = clone_node(tr[id].rs);
tr[id].ls = arr;
tr[id].rs = b;
apply_here(arr, ll, mul, add);
apply_here(b, lr, mul, add);
tr[id].mul = T(1);
tr[id].add = T(0);
return true;
}
void pull(int id) { tr[id].sum = tr[tr[id].ls].sum + tr[tr[id].rs].sum; }
int apply_node(int id, int l, int r, int ql, int qr, T mul, T add,
bool owned = false) {
if (qr <= l || r <= ql) {
return id;
}
int res = owned ? id : clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = l + (r - l) / 2;
bool fresh = push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add, fresh);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add, fresh);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr, T sm, T sa,
bool owned = false) {
if (qr <= l || r <= ql || (dst == src && sm == T(1) && sa == T(0))) {
return dst;
}
if (ql <= l && r <= qr) {
if (sm == T(1) && sa == T(0)) {
return src;
}
int res = clone_node(src);
apply_here(res, r - l, sm, sa);
return res;
}
int mid = l + (r - l) / 2;
int dc = owned ? dst : clone_node(dst);
bool fresh = push_cloned(dc, mid - l, r - mid);
T mul = sm * tr[src].mul;
T add = sm * tr[src].add + sa;
int arr = copy_node(tr[dc].ls, tr[src].ls, l, mid, ql, qr, mul, add, fresh);
int b = copy_node(tr[dc].rs, tr[src].rs, mid, r, ql, qr, mul, add, fresh);
tr[dc].ls = arr;
tr[dc].rs = b;
pull(dc);
return dc;
}
T prod_node(int id, int l, int r, int ql, int qr, T am, T aa) const {
if (qr <= l || r <= ql) {
return T(0);
}
if (ql <= l && r <= qr) {
return am * tr[id].sum + aa * T(r - l);
}
T mul = am * tr[id].mul;
T add = am * tr[id].add + aa;
int mid = l + (r - l) / 2;
if (qr <= mid) {
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add);
}
if (mid <= ql) {
return prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
return prod_node(tr[id].ls, l, mid, ql, qr, mul, add) +
prod_node(tr[id].rs, mid, r, ql, qr, mul, add);
}
};
} // namespace noya
// NOYA_PERSISTENT_AFFINE_SEGTREE_HPP