offline_dynamic_component_sum.hpp¶
离线加删边、点权增量与分量和；压缩查询时间、合并平行边区间，普通整数增量只处理一次并用 128 位累计。
Complexity: Time: \(O(V + Q \log (Q + 1) + (E \log (K + 1) + U + K) \log (V + 1))\) for \(\le 64\)-bit integers; other \(T\) adds \(O(U \log (K + 1) \log (V + 1))\). Space: \(O(V + Q + E \log (K + 1))\) for \(\le 64\)-bit integers, plus \(O(U \log (K + 1))\) for other \(T\). \(K\) queries, \(E\) edge lifetimes, \(U\) increments.
AC 记录：dynamic_graph_vertex_add_component_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+U+K) log(V+1)) for <=64-bit integers;
/// other T adds O(U log(K+1) log(V+1)). Space: O(V+Q+E log(K+1)) for <=64-bit integers,
/// plus O(U log(K+1)) for other T. K queries, E edge lifetimes, U increments.
#include <algorithm>
#include <cassert>
#include <limits>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Edge lifetimes cover query times.
/// Parallel copies share one lifetime while their multiplicity stays positive.
/// A depth-first traversal applies those operations to a union-find
/// whose merges can be rolled back. Integer increments persist in chronological
/// order; other T uses rollback of increment intervals and needs only +=.
/// T's addition must be associative and commutative. solve() preserves events.
/// <=64-bit integers accumulate in 128 bits; signed query answers must fit T.
/// Other T must represent its intermediate sums.
template <class T> struct offline_dynamic_component_sum {
enum class event_type { add_edge, remove_edge, add_value, query_sum };
struct event {
event_type ty;
int a;
int b = -1;
T val{};
int qid = -1;
};
std::vector<T> iv;
std::vector<event> ev;
int qn = 0;
offline_dynamic_component_sum() = default;
explicit offline_dynamic_component_sum(std::vector<T> va1)
: iv(std::move(va1)) {}
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add_edge, a, b});
}
/// @brief Record the removal of the most recently inserted active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove_edge, a, b});
}
/// @brief Add delta to one vertex from this time onward.
void add_vertex(int u, const T &dlt) {
check_vertex(u);
ev.push_back({event_type::add_value, u, -1, dlt});
}
/// @brief Record a component-sum query and return its answer index.
int add_query(int u) {
check_vertex(u);
int id = qn++;
ev.push_back({event_type::query_sum, u, -1, T{}, id});
return id;
}
/// @brief Solve all recorded component-sum queries.
std::vector<T> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg(2 * base);
auto insert = [&](int begin, int end, int id) {
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
auto it = active.try_emplace(edge, active_edge{0, time, i}).first;
++it->second.count;
} else if (cur.ty == event_type::remove_edge) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else if (cur.ty == event_type::add_value) {
if constexpr (!persistent_values) insert(time, qn, i);
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
int cursor = 0;
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
auto state = dsu.snapshot();
for (int id : seg[nd]) {
const auto &cur = ev[id];
if (cur.ty == event_type::add_value) dsu.add_vertex(cur.a, cur.val);
else dsu.merge(cur.a, cur.b);
}
if (r - l == 1) {
if constexpr (persistent_values) {
while (cursor < queries[l]) {
const auto &update = ev[cursor++];
if (update.ty == event_type::add_value)
dsu.add_vertex(update.a, update.val);
}
}
const auto &cur = ev[queries[l]];
ans[cur.qid] = dsu.component_sum(cur.a);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
return ans;
}
private:
static constexpr bool persistent_values =
std::is_integral_v<T> && !std::is_same_v<T, bool> && sizeof(T) <= 8;
using total_type = std::conditional_t<persistent_values,
std::conditional_t<std::is_signed_v<T>, __int128, unsigned __int128>, T>;
struct rollback_component_dsu {
struct change {
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<total_type> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1.begin(), va1.end()) {}
int leader(int u) const {
while (par[u] >= 0) {
u = par[u];
}
return u;
}
void merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) return;
if (-par[a] < -par[b]) {
std::swap(a, b);
}
if constexpr (persistent_values)
his.push_back({a, par[a], b, par[b], T{}});
else
his.push_back({a, par[a], b, par[b], sum[a]});
par[a] += par[b];
par[b] = a;
sum[a] += sum[b];
}
void add_vertex(int u, const T &dlt) {
if constexpr (persistent_values) {
// Every DSU ancestor retains its subtree's current vertex total.
while (true) {
sum[u] += dlt;
if (par[u] < 0) break;
u = par[u];
}
} else {
int rt = leader(u);
his.push_back({rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
}
T component_sum(int u) const {
const auto &value = sum[leader(u)];
if constexpr (persistent_values && std::is_signed_v<T>) {
assert(value >= std::numeric_limits<T>::min() &&
value <= std::numeric_limits<T>::max());
}
return T(value);
}
std::size_t snapshot() const { return his.size(); }
void rollback(std::size_t st) {
while (his.size() > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.b != -1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
if constexpr (persistent_values) sum[lst.a] -= sum[lst.b];
}
if constexpr (!persistent_values) sum[lst.a] = std::move(lst.ps);
}
}
};
void check_vertex(int u) const { assert(0 <= u && u < int(iv.size())); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya
// NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP
#ifndef NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP
#define NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP 1
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+U+K) log(V+1)) for <=64-bit integers;
/// other T adds O(U log(K+1) log(V+1)). Space: O(V+Q+E log(K+1)) for <=64-bit integers,
/// plus O(U log(K+1)) for other T. K queries, E edge lifetimes, U increments.
#include <algorithm>
#include <cassert>
#include <limits>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Edge lifetimes cover query times.
/// Parallel copies share one lifetime while their multiplicity stays positive.
/// A depth-first traversal applies those operations to a union-find
/// whose merges can be rolled back. Integer increments persist in chronological
/// order; other T uses rollback of increment intervals and needs only +=.
/// T's addition must be associative and commutative. solve() preserves events.
/// <=64-bit integers accumulate in 128 bits; signed query answers must fit T.
/// Other T must represent its intermediate sums.
template <class T> struct offline_dynamic_component_sum {
enum class event_type { add_edge, remove_edge, add_value, query_sum };
struct event {
event_type ty;
int a;
int b = -1;
T val{};
int qid = -1;
};
std::vector<T> iv;
std::vector<event> ev;
int qn = 0;
offline_dynamic_component_sum() = default;
explicit offline_dynamic_component_sum(std::vector<T> va1)
: iv(std::move(va1)) {}
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add_edge, a, b});
}
/// @brief Record the removal of the most recently inserted active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove_edge, a, b});
}
/// @brief Add delta to one vertex from this time onward.
void add_vertex(int u, const T &dlt) {
check_vertex(u);
ev.push_back({event_type::add_value, u, -1, dlt});
}
/// @brief Record a component-sum query and return its answer index.
int add_query(int u) {
check_vertex(u);
int id = qn++;
ev.push_back({event_type::query_sum, u, -1, T{}, id});
return id;
}
/// @brief Solve all recorded component-sum queries.
std::vector<T> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg(2 * base);
auto insert = [&](int begin, int end, int id) {
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
auto it = active.try_emplace(edge, active_edge{0, time, i}).first;
++it->second.count;
} else if (cur.ty == event_type::remove_edge) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else if (cur.ty == event_type::add_value) {
if constexpr (!persistent_values) insert(time, qn, i);
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
int cursor = 0;
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
auto state = dsu.snapshot();
for (int id : seg[nd]) {
const auto &cur = ev[id];
if (cur.ty == event_type::add_value) dsu.add_vertex(cur.a, cur.val);
else dsu.merge(cur.a, cur.b);
}
if (r - l == 1) {
if constexpr (persistent_values) {
while (cursor < queries[l]) {
const auto &update = ev[cursor++];
if (update.ty == event_type::add_value)
dsu.add_vertex(update.a, update.val);
}
}
const auto &cur = ev[queries[l]];
ans[cur.qid] = dsu.component_sum(cur.a);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
return ans;
}
private:
static constexpr bool persistent_values =
std::is_integral_v<T> && !std::is_same_v<T, bool> && sizeof(T) <= 8;
using total_type = std::conditional_t<persistent_values,
std::conditional_t<std::is_signed_v<T>, __int128, unsigned __int128>, T>;
struct rollback_component_dsu {
struct change {
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<total_type> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1.begin(), va1.end()) {}
int leader(int u) const {
while (par[u] >= 0) {
u = par[u];
}
return u;
}
void merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) return;
if (-par[a] < -par[b]) {
std::swap(a, b);
}
if constexpr (persistent_values)
his.push_back({a, par[a], b, par[b], T{}});
else
his.push_back({a, par[a], b, par[b], sum[a]});
par[a] += par[b];
par[b] = a;
sum[a] += sum[b];
}
void add_vertex(int u, const T &dlt) {
if constexpr (persistent_values) {
// Every DSU ancestor retains its subtree's current vertex total.
while (true) {
sum[u] += dlt;
if (par[u] < 0) break;
u = par[u];
}
} else {
int rt = leader(u);
his.push_back({rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
}
T component_sum(int u) const {
const auto &value = sum[leader(u)];
if constexpr (persistent_values && std::is_signed_v<T>) {
assert(value >= std::numeric_limits<T>::min() &&
value <= std::numeric_limits<T>::max());
}
return T(value);
}
std::size_t snapshot() const { return his.size(); }
void rollback(std::size_t st) {
while (his.size() > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.b != -1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
if constexpr (persistent_values) sum[lst.a] -= sum[lst.b];
}
if constexpr (!persistent_values) sum[lst.a] = std::move(lst.ps);
}
}
};
void check_vertex(int u) const { assert(0 <= u && u < int(iv.size())); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya
#endif // NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP
/// @complexity Time: O(V+Q log(Q+1)+(E log(K+1)+U+K) log(V+1)) for <=64-bit integers;
/// other T adds O(U log(K+1) log(V+1)). Space: O(V+Q+E log(K+1)) for <=64-bit integers,
/// plus O(U log(K+1)) for other T. K queries, E edge lifetimes, U increments.
#include <algorithm>
#include <cassert>
#include <limits>
#include <map>
#include <type_traits>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Edge lifetimes cover query times.
/// Parallel copies share one lifetime while their multiplicity stays positive.
/// A depth-first traversal applies those operations to a union-find
/// whose merges can be rolled back. Integer increments persist in chronological
/// order; other T uses rollback of increment intervals and needs only +=.
/// T's addition must be associative and commutative. solve() preserves events.
/// <=64-bit integers accumulate in 128 bits; signed query answers must fit T.
/// Other T must represent its intermediate sums.
template <class T> struct offline_dynamic_component_sum {
enum class event_type { add_edge, remove_edge, add_value, query_sum };
struct event {
event_type ty;
int a;
int b = -1;
T val{};
int qid = -1;
};
std::vector<T> iv;
std::vector<event> ev;
int qn = 0;
offline_dynamic_component_sum() = default;
explicit offline_dynamic_component_sum(std::vector<T> va1)
: iv(std::move(va1)) {}
/// @brief Record the insertion of one copy of an undirected edge.
void add_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::add_edge, a, b});
}
/// @brief Record the removal of the most recently inserted active copy.
void remove_edge(int a, int b) {
check_vertex(a);
check_vertex(b);
normalize(a, b);
ev.push_back({event_type::remove_edge, a, b});
}
/// @brief Add delta to one vertex from this time onward.
void add_vertex(int u, const T &dlt) {
check_vertex(u);
ev.push_back({event_type::add_value, u, -1, dlt});
}
/// @brief Record a component-sum query and return its answer index.
int add_query(int u) {
check_vertex(u);
int id = qn++;
ev.push_back({event_type::query_sum, u, -1, T{}, id});
return id;
}
/// @brief Solve all recorded component-sum queries.
std::vector<T> solve() const {
if (qn == 0) return {};
std::size_t base = 1;
while (base < std::size_t(qn)) base *= 2;
std::vector<std::vector<int>> seg(2 * base);
auto insert = [&](int begin, int end, int id) {
for (std::size_t l = base + begin, r = base + end; l < r; l /= 2, r /= 2) {
if (l & 1) seg[l++].push_back(id);
if (r & 1) seg[--r].push_back(id);
}
};
struct active_edge { int count, start, id; };
std::map<std::pair<int, int>, active_edge> active;
std::vector<int> queries;
queries.reserve(qn);
for (int i = 0; i < int(ev.size()); ++i) {
const auto &cur = ev[i];
int time = int(queries.size());
auto edge = std::pair{cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
auto it = active.try_emplace(edge, active_edge{0, time, i}).first;
++it->second.count;
} else if (cur.ty == event_type::remove_edge) {
auto it = active.find(edge);
assert(it != active.end());
if (it == active.end()) continue;
if (--it->second.count == 0) {
if (cur.a != cur.b) insert(it->second.start, time, i);
active.erase(it);
}
} else if (cur.ty == event_type::add_value) {
if constexpr (!persistent_values) insert(time, qn, i);
} else {
queries.push_back(i);
}
}
for (const auto &[edge, state] : active)
if (edge.first != edge.second) insert(state.start, qn, state.id);
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
int cursor = 0;
auto dfs = [&](auto &self, std::size_t nd, std::size_t l, std::size_t r) -> void {
if (l >= std::size_t(qn)) return;
auto state = dsu.snapshot();
for (int id : seg[nd]) {
const auto &cur = ev[id];
if (cur.ty == event_type::add_value) dsu.add_vertex(cur.a, cur.val);
else dsu.merge(cur.a, cur.b);
}
if (r - l == 1) {
if constexpr (persistent_values) {
while (cursor < queries[l]) {
const auto &update = ev[cursor++];
if (update.ty == event_type::add_value)
dsu.add_vertex(update.a, update.val);
}
}
const auto &cur = ev[queries[l]];
ans[cur.qid] = dsu.component_sum(cur.a);
} else {
auto mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(state);
};
dfs(dfs, 1, 0, base);
return ans;
}
private:
static constexpr bool persistent_values =
std::is_integral_v<T> && !std::is_same_v<T, bool> && sizeof(T) <= 8;
using total_type = std::conditional_t<persistent_values,
std::conditional_t<std::is_signed_v<T>, __int128, unsigned __int128>, T>;
struct rollback_component_dsu {
struct change {
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<total_type> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1.begin(), va1.end()) {}
int leader(int u) const {
while (par[u] >= 0) {
u = par[u];
}
return u;
}
void merge(int a, int b) {
a = leader(a);
b = leader(b);
if (a == b) return;
if (-par[a] < -par[b]) {
std::swap(a, b);
}
if constexpr (persistent_values)
his.push_back({a, par[a], b, par[b], T{}});
else
his.push_back({a, par[a], b, par[b], sum[a]});
par[a] += par[b];
par[b] = a;
sum[a] += sum[b];
}
void add_vertex(int u, const T &dlt) {
if constexpr (persistent_values) {
// Every DSU ancestor retains its subtree's current vertex total.
while (true) {
sum[u] += dlt;
if (par[u] < 0) break;
u = par[u];
}
} else {
int rt = leader(u);
his.push_back({rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
}
T component_sum(int u) const {
const auto &value = sum[leader(u)];
if constexpr (persistent_values && std::is_signed_v<T>) {
assert(value >= std::numeric_limits<T>::min() &&
value <= std::numeric_limits<T>::max());
}
return T(value);
}
std::size_t snapshot() const { return his.size(); }
void rollback(std::size_t st) {
while (his.size() > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.b != -1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
if constexpr (persistent_values) sum[lst.a] -= sum[lst.b];
}
if constexpr (!persistent_values) sum[lst.a] = std::move(lst.ps);
}
}
};
void check_vertex(int u) const { assert(0 <= u && u < int(iv.size())); }
static void normalize(int &a, int &b) {
if (a > b) {
std::swap(a, b);
}
}
};
} // namespace noya
// NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP