offline_dynamic_component_sum.hpp¶
离线处理动态加删边、点权修改与连通块权值和查询；适合图随时间变化的分量统计。
Complexity: Time: O(Q log Q log V) for Q operations on V vertices. Space: O(Q log Q + V).
AC 记录：dynamic_graph_vertex_add_component_sum。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(Q log Q log V) for Q operations on V vertices.
/// Space: O(Q log Q + V).
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Every edge and every vertex increment is
/// placed on the segment-tree nodes covering the time interval where it is
/// active. A depth-first traversal applies those operations to a union-find
/// whose parent links and component sums can both be rolled back, so each leaf
/// sees exactly the graph and values at that query time.
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 {
int nt = int(ev.size());
if (nt == 0) {
return std::vector<T>(qn);
}
std::vector<std::vector<std::pair<int, int>>> seg(4 * nt);
std::vector<std::vector<std::pair<int, T>>> at(4 * nt);
auto aei = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
auto avi = [&](auto &self, int nd, int l, int r, int ql, int u,
const T &dlt) -> void {
if (r <= ql) {
return;
}
if (ql <= l) {
at[nd].emplace_back(u, dlt);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, u, dlt);
self(self, nd * 2 + 1, mid, r, ql, u, dlt);
};
std::map<std::pair<int, int>, std::vector<int>> ae;
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
ae[e].push_back(tm);
} else if (cur.ty == event_type::remove_edge) {
auto it = ae.find(e);
assert(it != ae.end() && !it->second.empty());
if (it == ae.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
aei(aei, 1, 0, nt, s, tm, e);
} else if (cur.ty == event_type::add_value) {
avi(avi, 1, 0, nt, tm, cur.a, cur.val);
}
}
for (const auto &[e, sta] : ae) {
for (int s : sta) {
aei(aei, 1, 0, nt, s, nt, e);
}
}
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
for (const auto &[u, dlt] : at[nd]) {
dsu.add_vertex(u, dlt);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query_sum) {
ans[cur.qid] = dsu.component_sum(cur.a);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
dfs(dfs, 1, 0, nt);
return ans;
}
private:
struct rollback_component_dsu {
struct change {
int ty1;
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<T> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1) {}
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) {
his.push_back({0, -1, 0, -1, 0, T{}});
return;
}
if (-par[a] < -par[b]) {
std::swap(a, b);
}
his.push_back({1, 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) {
int rt = leader(u);
his.push_back({2, rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
T component_sum(int u) const { return sum[leader(u)]; }
int snapshot() const { return int(his.size()); }
void rollback(int st) {
while (int(his.size()) > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.ty1 == 1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
sum[lst.a] = std::move(lst.ps);
} else if (lst.ty1 == 2) {
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
#ifndef NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP
#define NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP 1
/// @complexity Time: O(Q log Q log V) for Q operations on V vertices.
/// Space: O(Q log Q + V).
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Every edge and every vertex increment is
/// placed on the segment-tree nodes covering the time interval where it is
/// active. A depth-first traversal applies those operations to a union-find
/// whose parent links and component sums can both be rolled back, so each leaf
/// sees exactly the graph and values at that query time.
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 {
int nt = int(ev.size());
if (nt == 0) {
return std::vector<T>(qn);
}
std::vector<std::vector<std::pair<int, int>>> seg(4 * nt);
std::vector<std::vector<std::pair<int, T>>> at(4 * nt);
auto aei = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
auto avi = [&](auto &self, int nd, int l, int r, int ql, int u,
const T &dlt) -> void {
if (r <= ql) {
return;
}
if (ql <= l) {
at[nd].emplace_back(u, dlt);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, u, dlt);
self(self, nd * 2 + 1, mid, r, ql, u, dlt);
};
std::map<std::pair<int, int>, std::vector<int>> ae;
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
ae[e].push_back(tm);
} else if (cur.ty == event_type::remove_edge) {
auto it = ae.find(e);
assert(it != ae.end() && !it->second.empty());
if (it == ae.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
aei(aei, 1, 0, nt, s, tm, e);
} else if (cur.ty == event_type::add_value) {
avi(avi, 1, 0, nt, tm, cur.a, cur.val);
}
}
for (const auto &[e, sta] : ae) {
for (int s : sta) {
aei(aei, 1, 0, nt, s, nt, e);
}
}
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
for (const auto &[u, dlt] : at[nd]) {
dsu.add_vertex(u, dlt);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query_sum) {
ans[cur.qid] = dsu.component_sum(cur.a);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
dfs(dfs, 1, 0, nt);
return ans;
}
private:
struct rollback_component_dsu {
struct change {
int ty1;
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<T> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1) {}
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) {
his.push_back({0, -1, 0, -1, 0, T{}});
return;
}
if (-par[a] < -par[b]) {
std::swap(a, b);
}
his.push_back({1, 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) {
int rt = leader(u);
his.push_back({2, rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
T component_sum(int u) const { return sum[leader(u)]; }
int snapshot() const { return int(his.size()); }
void rollback(int st) {
while (int(his.size()) > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.ty1 == 1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
sum[lst.a] = std::move(lst.ps);
} else if (lst.ty1 == 2) {
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
#include <algorithm>
#include <cassert>
#include <map>
#include <utility>
#include <vector>
/// @complexity Time: O(Q log Q log V) for Q operations on V vertices.
/// Space: O(Q log Q + V).
namespace noya {
/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Every edge and every vertex increment is
/// placed on the segment-tree nodes covering the time interval where it is
/// active. A depth-first traversal applies those operations to a union-find
/// whose parent links and component sums can both be rolled back, so each leaf
/// sees exactly the graph and values at that query time.
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 {
int nt = int(ev.size());
if (nt == 0) {
return std::vector<T>(qn);
}
std::vector<std::vector<std::pair<int, int>>> seg(4 * nt);
std::vector<std::vector<std::pair<int, T>>> at(4 * nt);
auto aei = [&](auto &self, int nd, int l, int r, int ql, int qr,
std::pair<int, int> e) -> void {
if (qr <= l || r <= ql) {
return;
}
if (ql <= l && r <= qr) {
seg[nd].push_back(e);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, qr, e);
self(self, nd * 2 + 1, mid, r, ql, qr, e);
};
auto avi = [&](auto &self, int nd, int l, int r, int ql, int u,
const T &dlt) -> void {
if (r <= ql) {
return;
}
if (ql <= l) {
at[nd].emplace_back(u, dlt);
return;
}
int mid = (l + r) / 2;
self(self, nd * 2, l, mid, ql, u, dlt);
self(self, nd * 2 + 1, mid, r, ql, u, dlt);
};
std::map<std::pair<int, int>, std::vector<int>> ae;
for (int tm = 0; tm < nt; tm++) {
const event &cur = ev[tm];
std::pair<int, int> e = {cur.a, cur.b};
if (cur.ty == event_type::add_edge) {
ae[e].push_back(tm);
} else if (cur.ty == event_type::remove_edge) {
auto it = ae.find(e);
assert(it != ae.end() && !it->second.empty());
if (it == ae.end() || it->second.empty()) {
continue;
}
int s = it->second.back();
it->second.pop_back();
aei(aei, 1, 0, nt, s, tm, e);
} else if (cur.ty == event_type::add_value) {
avi(avi, 1, 0, nt, tm, cur.a, cur.val);
}
}
for (const auto &[e, sta] : ae) {
for (int s : sta) {
aei(aei, 1, 0, nt, s, nt, e);
}
}
rollback_component_dsu dsu(iv);
std::vector<T> ans(qn);
auto dfs = [&](auto &self, int nd, int l, int r) -> void {
int st = dsu.snapshot();
for (auto [a, b] : seg[nd]) {
dsu.merge(a, b);
}
for (const auto &[u, dlt] : at[nd]) {
dsu.add_vertex(u, dlt);
}
if (r - l == 1) {
const event &cur = ev[l];
if (cur.ty == event_type::query_sum) {
ans[cur.qid] = dsu.component_sum(cur.a);
}
} else {
int mid = (l + r) / 2;
self(self, nd * 2, l, mid);
self(self, nd * 2 + 1, mid, r);
}
dsu.rollback(st);
};
dfs(dfs, 1, 0, nt);
return ans;
}
private:
struct rollback_component_dsu {
struct change {
int ty1;
int a;
int fa1;
int b;
int fa2;
T ps;
};
std::vector<int> par;
std::vector<T> sum;
std::vector<change> his;
explicit rollback_component_dsu(const std::vector<T> &va1)
: par(va1.size(), -1), sum(va1) {}
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) {
his.push_back({0, -1, 0, -1, 0, T{}});
return;
}
if (-par[a] < -par[b]) {
std::swap(a, b);
}
his.push_back({1, 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) {
int rt = leader(u);
his.push_back({2, rt, 0, -1, 0, sum[rt]});
sum[rt] += dlt;
}
T component_sum(int u) const { return sum[leader(u)]; }
int snapshot() const { return int(his.size()); }
void rollback(int st) {
while (int(his.size()) > st) {
change lst = std::move(his.back());
his.pop_back();
if (lst.ty1 == 1) {
par[lst.a] = lst.fa1;
par[lst.b] = lst.fa2;
sum[lst.a] = std::move(lst.ps);
} else if (lst.ty1 == 2) {
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