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.
/// Every update clones only its two boundary paths. A range copy descends in a
/// destination version and a source version together, replacing fully covered
/// destination nodes by the corresponding immutable source nodes. Lazy tags
/// are pushed only into freshly cloned nodes, 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(n * 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);
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);
return copy_node(dr, sr, 0, n, l, r);
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
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) / 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;
}
void push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return;
}
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);
}
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) {
if (qr <= l || r <= ql) {
return id;
}
int res = clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = (l + r) / 2;
push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int normalized_clone(int id, int ll, int lr) {
int res = clone_node(id);
push_cloned(res, ll, lr);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return dst;
}
if (ql <= l && r <= qr) {
return src;
}
int mid = (l + r) / 2;
int dc = normalized_clone(dst, mid - l, r - mid);
int sc = normalized_clone(src, mid - l, r - mid);
int arr = copy_node(tr[dc].ls, tr[sc].ls, l, mid, ql, qr);
int b = copy_node(tr[dc].rs, tr[sc].rs, mid, r, ql, qr);
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) / 2;
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
#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.
/// Every update clones only its two boundary paths. A range copy descends in a
/// destination version and a source version together, replacing fully covered
/// destination nodes by the corresponding immutable source nodes. Lazy tags
/// are pushed only into freshly cloned nodes, 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(n * 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);
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);
return copy_node(dr, sr, 0, n, l, r);
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
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) / 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;
}
void push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return;
}
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);
}
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) {
if (qr <= l || r <= ql) {
return id;
}
int res = clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = (l + r) / 2;
push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int normalized_clone(int id, int ll, int lr) {
int res = clone_node(id);
push_cloned(res, ll, lr);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return dst;
}
if (ql <= l && r <= qr) {
return src;
}
int mid = (l + r) / 2;
int dc = normalized_clone(dst, mid - l, r - mid);
int sc = normalized_clone(src, mid - l, r - mid);
int arr = copy_node(tr[dc].ls, tr[sc].ls, l, mid, ql, qr);
int b = copy_node(tr[dc].rs, tr[sc].rs, mid, r, ql, qr);
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) / 2;
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
#include <cassert>
#include <vector>
/// @complexity Time: O(log n) per range affine update, range copy, or query.
/// Space: O(n + q log n) nodes for q derived versions.
namespace noya {
/// @brief Persistent lazy segment tree for range affine transforms and sums.
/// Every update clones only its two boundary paths. A range copy descends in a
/// destination version and a source version together, replacing fully covered
/// destination nodes by the corresponding immutable source nodes. Lazy tags
/// are pushed only into freshly cloned nodes, 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(n * 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);
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);
return copy_node(dr, sr, 0, n, l, r);
}
T prod(int rt, int l, int r) const {
assert(valid_root(rt));
assert(0 <= l && l <= r && r <= n);
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) / 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;
}
void push_cloned(int id, int ll, int lr) {
if (tr[id].ls < 0) {
return;
}
T mul = tr[id].mul;
T add = tr[id].add;
if (mul == T(1) && add == T(0)) {
return;
}
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);
}
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) {
if (qr <= l || r <= ql) {
return id;
}
int res = clone_node(id);
if (ql <= l && r <= qr) {
apply_here(res, r - l, mul, add);
return res;
}
int mid = (l + r) / 2;
push_cloned(res, mid - l, r - mid);
int arr = apply_node(tr[res].ls, l, mid, ql, qr, mul, add);
int b = apply_node(tr[res].rs, mid, r, ql, qr, mul, add);
tr[res].ls = arr;
tr[res].rs = b;
pull(res);
return res;
}
int normalized_clone(int id, int ll, int lr) {
int res = clone_node(id);
push_cloned(res, ll, lr);
return res;
}
int copy_node(int dst, int src, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return dst;
}
if (ql <= l && r <= qr) {
return src;
}
int mid = (l + r) / 2;
int dc = normalized_clone(dst, mid - l, r - mid);
int sc = normalized_clone(src, mid - l, r - mid);
int arr = copy_node(tr[dc].ls, tr[sc].ls, l, mid, ql, qr);
int b = copy_node(tr[dc].rs, tr[sc].rs, mid, r, ql, qr);
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) / 2;
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