tree_contour.hpp¶
静态树上维护点加/距离区间和、距离区间加/单点取值两套独立状态；点分治复用子树大小，按距离累加后线性建 Fenwick，构造 \(O(n\log n)\)。
Complexity: Time: \(O(n \log n)\) construction and \(O(\log^{2} n)\) per update or query. Space: \(O(n \log n)\); \(O(n)\) recursive depth during construction.
AC 记录：vertex_add_range_contour_sum_on_tree, vertex_get_range_contour_add_on_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n) construction and O(log^2 n) per update or
/// query. Space: O(n log n); O(n) recursive depth during construction.
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
namespace noya {
/// @brief Maintain values indexed by tree distance. Every vertex is recorded
/// in all centroid-ancestor buckets; querying adds all buckets and subtracts
/// the bucket of the branch containing the query vertex. Fenwick trees over
/// distances support two independent channels: point-add/range-sum and
/// range-add/point-get. Both start from the supplied initial values; updates in
/// one channel do not affect the other. Intervals are half-open [l,r), including
/// arbitrary int endpoints (negative distances simply contain no vertices).
/// Input must be an undirected tree with valid endpoints, or empty; it is not
/// retained or modified. Initial values are empty (all zero) or have size n.
/// Vertex count is at most INT_MAX-2. Values, negated updates, bucket sums and
/// arithmetic intermediates must fit long long. Construction uses 512 MiB
/// stacks in local tests. Copies own independent state.
class tree_contour {
struct fenwick {
std::vector<long long> dat;
fenwick() = default;
explicit fenwick(int siz) : dat(siz + 1) {}
int size() const { return int(dat.size()) - 1; }
// Convert the per-distance entries to a Fenwick tree in linear time.
void build() {
for (std::size_t i = 1; i < dat.size(); ++i) {
std::size_t parent = i + (i & -i);
if (parent < dat.size()) dat[parent] += dat[i];
}
}
void add(int i, long long val) {
assert(0 <= i && i < size());
for (std::size_t k = std::size_t(i) + 1; k < dat.size(); k += k & -k) {
dat[k] += val;
}
}
long long prefix_sum(int cnt) const {
cnt = std::clamp(cnt, 0, size());
long long res = 0;
for (; cnt > 0; cnt -= cnt & -cnt) {
res += dat[cnt];
}
return res;
}
};
struct bucket {
int nd = 0;
fenwick bit;
fenwick tag;
void reset(int cnt) {
nd = cnt;
bit = fenwick(cnt);
tag = fenwick(cnt + 1);
}
void point_add(int dis, long long val) { bit.add(dis, val); }
long long point_prefix(int lim) const { return bit.prefix_sum(lim); }
void range_add(int l, int r, long long val) {
l = std::clamp(l, 0, nd);
r = std::clamp(r, 0, nd);
if (l >= r) {
return;
}
tag.add(l, val);
tag.add(r, -val);
}
long long point_tag(int dis) const {
assert(0 <= dis && dis < nd);
return tag.prefix_sum(dis + 1);
}
};
struct ancestor_entry {
int cen = -1;
int dis = 0;
int br = -1;
};
int n_ = 0;
std::vector<std::vector<ancestor_entry>> up_;
std::vector<bucket> a_;
std::vector<std::vector<bucket>> br_;
std::vector<long long> iv;
public:
explicit tree_contour(const std::vector<std::vector<int>> &g,
const std::vector<long long> &iv1 = {})
: n_(int(g.size())), up_(n_), a_(n_), br_(n_),
iv(iv1.empty() ? std::vector<long long>(n_) : iv1) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
assert(iv.size() == g.size());
if (n_ == 0) {
return;
}
std::vector<int> size(n_, 1);
std::vector<char> removed(n_);
auto init = [&](auto &self, int u, int parent) -> void {
for (int v : g[u]) if (v != parent) {
assert(0 <= v && v < n_);
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto decompose = [&](auto &self, int entry) -> void {
int total = size[entry], cen = entry;
for (;;) {
int next = -1;
for (int v : g[cen]) if (!removed[v] && size[v] > total / 2) {
next = v;
break;
}
if (next == -1) break;
// Reroot sizes across this edge; they remain valid for child components.
size[cen] -= size[next];
size[next] += size[cen];
cen = next;
}
removed[cen] = true;
up_[cen].push_back({cen, 0, -1});
int maximum = 0;
for (int v : g[cen]) if (!removed[v]) {
int branch = int(br_[cen].size());
auto collect = [&](auto &walk, int u, int parent, int distance) -> int {
up_[u].push_back({cen, distance, branch});
int farthest = distance;
for (int w : g[u]) if (!removed[w] && w != parent)
farthest = std::max(farthest, walk(walk, w, u, distance + 1));
return farthest;
};
int farthest = collect(collect, v, cen, 1);
br_[cen].push_back({});
br_[cen].back().reset(farthest + 1);
maximum = std::max(maximum, farthest);
}
a_[cen].reset(maximum + 1);
for (int v : g[cen]) if (!removed[v]) self(self, v);
};
decompose(decompose, 0);
if (!iv1.empty()) {
for (int u = 0; u < n_; ++u) {
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].bit.dat[ent.dis + 1] += iv[u];
if (ent.br != -1)
br_[ent.cen][ent.br].bit.dat[ent.dis + 1] += iv[u];
}
}
for (int cen = 0; cen < n_; ++cen) {
a_[cen].bit.build();
for (auto &branch : br_[cen]) branch.bit.build();
}
}
}
/// @brief Add value to one vertex for later contour-sum queries.
void point_add(int u, long long val) {
assert(0 <= u && u < n_);
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].point_add(ent.dis, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].point_add(ent.dis, val);
}
}
}
/// @brief Sum values at vertices whose distance from vertex is in [l,r).
long long range_sum(int u, int l, int r) const {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return 0;
long long res = 0;
for (const ancestor_entry &ent : up_[u]) {
int hi = r - ent.dis;
if (hi <= 0) continue;
int lo = l - ent.dis;
res += a_[ent.cen].point_prefix(hi) - a_[ent.cen].point_prefix(lo);
if (ent.br != -1)
res -= br_[ent.cen][ent.br].point_prefix(hi)
- br_[ent.cen][ent.br].point_prefix(lo);
}
return res;
}
/// @brief Add value to vertices whose distance from vertex is in [l,r).
void range_add(int u, int l, int r, long long val) {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return;
for (const ancestor_entry &ent : up_[u]) {
int ql = l - ent.dis;
int qr = r - ent.dis;
a_[ent.cen].range_add(ql, qr, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].range_add(ql, qr, val);
}
}
}
/// @brief Return the initial value plus every contour-range addition that
/// contains this vertex.
long long point_get(int u) const {
assert(0 <= u && u < n_);
long long res = iv[u];
for (const ancestor_entry &ent : up_[u]) {
res += a_[ent.cen].point_tag(ent.dis);
if (ent.br != -1) {
res -= br_[ent.cen][ent.br].point_tag(ent.dis);
}
}
return res;
}
};
} // namespace noya
// NOYA_TREE_CONTOUR_HPP
#ifndef NOYA_TREE_CONTOUR_HPP
#define NOYA_TREE_CONTOUR_HPP 1
/// @complexity Time: O(n log n) construction and O(log^2 n) per update or
/// query. Space: O(n log n); O(n) recursive depth during construction.
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
namespace noya {
/// @brief Maintain values indexed by tree distance. Every vertex is recorded
/// in all centroid-ancestor buckets; querying adds all buckets and subtracts
/// the bucket of the branch containing the query vertex. Fenwick trees over
/// distances support two independent channels: point-add/range-sum and
/// range-add/point-get. Both start from the supplied initial values; updates in
/// one channel do not affect the other. Intervals are half-open [l,r), including
/// arbitrary int endpoints (negative distances simply contain no vertices).
/// Input must be an undirected tree with valid endpoints, or empty; it is not
/// retained or modified. Initial values are empty (all zero) or have size n.
/// Vertex count is at most INT_MAX-2. Values, negated updates, bucket sums and
/// arithmetic intermediates must fit long long. Construction uses 512 MiB
/// stacks in local tests. Copies own independent state.
class tree_contour {
struct fenwick {
std::vector<long long> dat;
fenwick() = default;
explicit fenwick(int siz) : dat(siz + 1) {}
int size() const { return int(dat.size()) - 1; }
// Convert the per-distance entries to a Fenwick tree in linear time.
void build() {
for (std::size_t i = 1; i < dat.size(); ++i) {
std::size_t parent = i + (i & -i);
if (parent < dat.size()) dat[parent] += dat[i];
}
}
void add(int i, long long val) {
assert(0 <= i && i < size());
for (std::size_t k = std::size_t(i) + 1; k < dat.size(); k += k & -k) {
dat[k] += val;
}
}
long long prefix_sum(int cnt) const {
cnt = std::clamp(cnt, 0, size());
long long res = 0;
for (; cnt > 0; cnt -= cnt & -cnt) {
res += dat[cnt];
}
return res;
}
};
struct bucket {
int nd = 0;
fenwick bit;
fenwick tag;
void reset(int cnt) {
nd = cnt;
bit = fenwick(cnt);
tag = fenwick(cnt + 1);
}
void point_add(int dis, long long val) { bit.add(dis, val); }
long long point_prefix(int lim) const { return bit.prefix_sum(lim); }
void range_add(int l, int r, long long val) {
l = std::clamp(l, 0, nd);
r = std::clamp(r, 0, nd);
if (l >= r) {
return;
}
tag.add(l, val);
tag.add(r, -val);
}
long long point_tag(int dis) const {
assert(0 <= dis && dis < nd);
return tag.prefix_sum(dis + 1);
}
};
struct ancestor_entry {
int cen = -1;
int dis = 0;
int br = -1;
};
int n_ = 0;
std::vector<std::vector<ancestor_entry>> up_;
std::vector<bucket> a_;
std::vector<std::vector<bucket>> br_;
std::vector<long long> iv;
public:
explicit tree_contour(const std::vector<std::vector<int>> &g,
const std::vector<long long> &iv1 = {})
: n_(int(g.size())), up_(n_), a_(n_), br_(n_),
iv(iv1.empty() ? std::vector<long long>(n_) : iv1) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
assert(iv.size() == g.size());
if (n_ == 0) {
return;
}
std::vector<int> size(n_, 1);
std::vector<char> removed(n_);
auto init = [&](auto &self, int u, int parent) -> void {
for (int v : g[u]) if (v != parent) {
assert(0 <= v && v < n_);
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto decompose = [&](auto &self, int entry) -> void {
int total = size[entry], cen = entry;
for (;;) {
int next = -1;
for (int v : g[cen]) if (!removed[v] && size[v] > total / 2) {
next = v;
break;
}
if (next == -1) break;
// Reroot sizes across this edge; they remain valid for child components.
size[cen] -= size[next];
size[next] += size[cen];
cen = next;
}
removed[cen] = true;
up_[cen].push_back({cen, 0, -1});
int maximum = 0;
for (int v : g[cen]) if (!removed[v]) {
int branch = int(br_[cen].size());
auto collect = [&](auto &walk, int u, int parent, int distance) -> int {
up_[u].push_back({cen, distance, branch});
int farthest = distance;
for (int w : g[u]) if (!removed[w] && w != parent)
farthest = std::max(farthest, walk(walk, w, u, distance + 1));
return farthest;
};
int farthest = collect(collect, v, cen, 1);
br_[cen].push_back({});
br_[cen].back().reset(farthest + 1);
maximum = std::max(maximum, farthest);
}
a_[cen].reset(maximum + 1);
for (int v : g[cen]) if (!removed[v]) self(self, v);
};
decompose(decompose, 0);
if (!iv1.empty()) {
for (int u = 0; u < n_; ++u) {
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].bit.dat[ent.dis + 1] += iv[u];
if (ent.br != -1)
br_[ent.cen][ent.br].bit.dat[ent.dis + 1] += iv[u];
}
}
for (int cen = 0; cen < n_; ++cen) {
a_[cen].bit.build();
for (auto &branch : br_[cen]) branch.bit.build();
}
}
}
/// @brief Add value to one vertex for later contour-sum queries.
void point_add(int u, long long val) {
assert(0 <= u && u < n_);
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].point_add(ent.dis, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].point_add(ent.dis, val);
}
}
}
/// @brief Sum values at vertices whose distance from vertex is in [l,r).
long long range_sum(int u, int l, int r) const {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return 0;
long long res = 0;
for (const ancestor_entry &ent : up_[u]) {
int hi = r - ent.dis;
if (hi <= 0) continue;
int lo = l - ent.dis;
res += a_[ent.cen].point_prefix(hi) - a_[ent.cen].point_prefix(lo);
if (ent.br != -1)
res -= br_[ent.cen][ent.br].point_prefix(hi)
- br_[ent.cen][ent.br].point_prefix(lo);
}
return res;
}
/// @brief Add value to vertices whose distance from vertex is in [l,r).
void range_add(int u, int l, int r, long long val) {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return;
for (const ancestor_entry &ent : up_[u]) {
int ql = l - ent.dis;
int qr = r - ent.dis;
a_[ent.cen].range_add(ql, qr, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].range_add(ql, qr, val);
}
}
}
/// @brief Return the initial value plus every contour-range addition that
/// contains this vertex.
long long point_get(int u) const {
assert(0 <= u && u < n_);
long long res = iv[u];
for (const ancestor_entry &ent : up_[u]) {
res += a_[ent.cen].point_tag(ent.dis);
if (ent.br != -1) {
res -= br_[ent.cen][ent.br].point_tag(ent.dis);
}
}
return res;
}
};
} // namespace noya
#endif // NOYA_TREE_CONTOUR_HPP
/// @complexity Time: O(n log n) construction and O(log^2 n) per update or
/// query. Space: O(n log n); O(n) recursive depth during construction.
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
namespace noya {
/// @brief Maintain values indexed by tree distance. Every vertex is recorded
/// in all centroid-ancestor buckets; querying adds all buckets and subtracts
/// the bucket of the branch containing the query vertex. Fenwick trees over
/// distances support two independent channels: point-add/range-sum and
/// range-add/point-get. Both start from the supplied initial values; updates in
/// one channel do not affect the other. Intervals are half-open [l,r), including
/// arbitrary int endpoints (negative distances simply contain no vertices).
/// Input must be an undirected tree with valid endpoints, or empty; it is not
/// retained or modified. Initial values are empty (all zero) or have size n.
/// Vertex count is at most INT_MAX-2. Values, negated updates, bucket sums and
/// arithmetic intermediates must fit long long. Construction uses 512 MiB
/// stacks in local tests. Copies own independent state.
class tree_contour {
struct fenwick {
std::vector<long long> dat;
fenwick() = default;
explicit fenwick(int siz) : dat(siz + 1) {}
int size() const { return int(dat.size()) - 1; }
// Convert the per-distance entries to a Fenwick tree in linear time.
void build() {
for (std::size_t i = 1; i < dat.size(); ++i) {
std::size_t parent = i + (i & -i);
if (parent < dat.size()) dat[parent] += dat[i];
}
}
void add(int i, long long val) {
assert(0 <= i && i < size());
for (std::size_t k = std::size_t(i) + 1; k < dat.size(); k += k & -k) {
dat[k] += val;
}
}
long long prefix_sum(int cnt) const {
cnt = std::clamp(cnt, 0, size());
long long res = 0;
for (; cnt > 0; cnt -= cnt & -cnt) {
res += dat[cnt];
}
return res;
}
};
struct bucket {
int nd = 0;
fenwick bit;
fenwick tag;
void reset(int cnt) {
nd = cnt;
bit = fenwick(cnt);
tag = fenwick(cnt + 1);
}
void point_add(int dis, long long val) { bit.add(dis, val); }
long long point_prefix(int lim) const { return bit.prefix_sum(lim); }
void range_add(int l, int r, long long val) {
l = std::clamp(l, 0, nd);
r = std::clamp(r, 0, nd);
if (l >= r) {
return;
}
tag.add(l, val);
tag.add(r, -val);
}
long long point_tag(int dis) const {
assert(0 <= dis && dis < nd);
return tag.prefix_sum(dis + 1);
}
};
struct ancestor_entry {
int cen = -1;
int dis = 0;
int br = -1;
};
int n_ = 0;
std::vector<std::vector<ancestor_entry>> up_;
std::vector<bucket> a_;
std::vector<std::vector<bucket>> br_;
std::vector<long long> iv;
public:
explicit tree_contour(const std::vector<std::vector<int>> &g,
const std::vector<long long> &iv1 = {})
: n_(int(g.size())), up_(n_), a_(n_), br_(n_),
iv(iv1.empty() ? std::vector<long long>(n_) : iv1) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max() - 2));
assert(iv.size() == g.size());
if (n_ == 0) {
return;
}
std::vector<int> size(n_, 1);
std::vector<char> removed(n_);
auto init = [&](auto &self, int u, int parent) -> void {
for (int v : g[u]) if (v != parent) {
assert(0 <= v && v < n_);
self(self, v, u);
size[u] += size[v];
}
};
init(init, 0, -1);
auto decompose = [&](auto &self, int entry) -> void {
int total = size[entry], cen = entry;
for (;;) {
int next = -1;
for (int v : g[cen]) if (!removed[v] && size[v] > total / 2) {
next = v;
break;
}
if (next == -1) break;
// Reroot sizes across this edge; they remain valid for child components.
size[cen] -= size[next];
size[next] += size[cen];
cen = next;
}
removed[cen] = true;
up_[cen].push_back({cen, 0, -1});
int maximum = 0;
for (int v : g[cen]) if (!removed[v]) {
int branch = int(br_[cen].size());
auto collect = [&](auto &walk, int u, int parent, int distance) -> int {
up_[u].push_back({cen, distance, branch});
int farthest = distance;
for (int w : g[u]) if (!removed[w] && w != parent)
farthest = std::max(farthest, walk(walk, w, u, distance + 1));
return farthest;
};
int farthest = collect(collect, v, cen, 1);
br_[cen].push_back({});
br_[cen].back().reset(farthest + 1);
maximum = std::max(maximum, farthest);
}
a_[cen].reset(maximum + 1);
for (int v : g[cen]) if (!removed[v]) self(self, v);
};
decompose(decompose, 0);
if (!iv1.empty()) {
for (int u = 0; u < n_; ++u) {
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].bit.dat[ent.dis + 1] += iv[u];
if (ent.br != -1)
br_[ent.cen][ent.br].bit.dat[ent.dis + 1] += iv[u];
}
}
for (int cen = 0; cen < n_; ++cen) {
a_[cen].bit.build();
for (auto &branch : br_[cen]) branch.bit.build();
}
}
}
/// @brief Add value to one vertex for later contour-sum queries.
void point_add(int u, long long val) {
assert(0 <= u && u < n_);
for (const ancestor_entry &ent : up_[u]) {
a_[ent.cen].point_add(ent.dis, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].point_add(ent.dis, val);
}
}
}
/// @brief Sum values at vertices whose distance from vertex is in [l,r).
long long range_sum(int u, int l, int r) const {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return 0;
long long res = 0;
for (const ancestor_entry &ent : up_[u]) {
int hi = r - ent.dis;
if (hi <= 0) continue;
int lo = l - ent.dis;
res += a_[ent.cen].point_prefix(hi) - a_[ent.cen].point_prefix(lo);
if (ent.br != -1)
res -= br_[ent.cen][ent.br].point_prefix(hi)
- br_[ent.cen][ent.br].point_prefix(lo);
}
return res;
}
/// @brief Add value to vertices whose distance from vertex is in [l,r).
void range_add(int u, int l, int r, long long val) {
assert(0 <= u && u < n_ && l <= r);
l = std::clamp(l, 0, n_);
r = std::clamp(r, 0, n_);
if (l == r) return;
for (const ancestor_entry &ent : up_[u]) {
int ql = l - ent.dis;
int qr = r - ent.dis;
a_[ent.cen].range_add(ql, qr, val);
if (ent.br != -1) {
br_[ent.cen][ent.br].range_add(ql, qr, val);
}
}
}
/// @brief Return the initial value plus every contour-range addition that
/// contains this vertex.
long long point_get(int u) const {
assert(0 <= u && u < n_);
long long res = iv[u];
for (const ancestor_entry &ent : up_[u]) {
res += a_[ent.cen].point_tag(ent.dis);
if (ent.br != -1) {
res -= br_[ent.cen][ent.br].point_tag(ent.dis);
}
}
return res;
}
};
} // namespace noya
// NOYA_TREE_CONTOUR_HPP