mergeable_frequency_tree.hpp¶
Dynamic frequency segment-tree pool supporting point updates, rank queries, destructive merging, and interval extraction in O(log U).
维护值域频次线段树并支持破坏性合并；适合树上启发式合并、子树频率和顺序统计。
Implementation¶
#ifndef NOYA_MERGEABLE_FREQUENCY_TREE_HPP
#define NOYA_MERGEABLE_FREQUENCY_TREE_HPP 1
/// @complexity Time: O(log U) update/query; O(min(nodes_a,nodes_b)) destructive merge.
/// Space: O(number of allocated nodes).
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Dynamic frequency segment-tree pool supporting point updates, rank
/// queries, destructive merging, and interval extraction in O(log U).
template <class Count = int> struct mergeable_frequency_tree {
struct node {
int left = 0;
int right = 0;
Count sum{};
};
int lower = 0;
int upper = 0;
std::vector<node> nodes{{}};
mergeable_frequency_tree() = default;
mergeable_frequency_tree(int lower_bound, int upper_bound)
: lower(lower_bound), upper(upper_bound) {
assert(lower < upper);
}
Count total(int root) const {
check_root(root);
return nodes[root].sum;
}
/// @brief Add delta at position, creating root and path nodes as needed.
void add(int &root, int position, Count delta) {
assert(lower <= position && position < upper);
add_impl(root, lower, upper, position, delta);
}
/// @brief Return the total frequency in [query_left, query_right).
Count count(int root, int query_left, int query_right) const {
check_root(root);
assert(lower <= query_left && query_left <= query_right &&
query_right <= upper);
return count_impl(root, lower, upper, query_left, query_right);
}
/// @brief Return the coordinate containing zero-indexed rank k.
int kth(int root, Count k) const {
check_root(root);
assert(Count{} <= k && k < nodes[root].sum);
int left_bound = lower;
int right_bound = upper;
while (right_bound - left_bound > 1) {
Count left_sum = nodes[nodes[root].left].sum;
int middle = std::midpoint(left_bound, right_bound);
if (k < left_sum) {
root = nodes[root].left;
right_bound = middle;
} else {
k -= left_sum;
root = nodes[root].right;
left_bound = middle;
}
}
return left_bound;
}
/// @brief Move every frequency in [query_left, query_right) from root into
/// a new root without duplicating leaves.
int extract(int &root, int query_left, int query_right) {
check_root(root);
assert(lower <= query_left && query_left <= query_right &&
query_right <= upper);
return extract_impl(root, lower, upper, query_left, query_right);
}
/// @brief Destructively merge source into destination and clear source.
void merge_into(int &destination, int &source) {
check_root(destination);
check_root(source);
if (destination == source && destination != 0) {
assert(false && "cannot merge a root into itself");
}
destination = merge_impl(destination, source);
source = 0;
}
private:
void check_root(int root) const {
assert(0 <= root && root < int(nodes.size()));
}
int make_node() {
nodes.push_back({});
return int(nodes.size()) - 1;
}
void pull(int root) {
nodes[root].sum =
nodes[nodes[root].left].sum + nodes[nodes[root].right].sum;
}
void add_impl(int &root, int left_bound, int right_bound, int position,
Count delta) {
if (root == 0) {
root = make_node();
}
if (right_bound - left_bound == 1) {
nodes[root].sum += delta;
assert(nodes[root].sum >= Count{});
return;
}
int middle = std::midpoint(left_bound, right_bound);
if (position < middle) {
int child = nodes[root].left;
add_impl(child, left_bound, middle, position, delta);
nodes[root].left = child;
} else {
int child = nodes[root].right;
add_impl(child, middle, right_bound, position, delta);
nodes[root].right = child;
}
pull(root);
}
Count count_impl(int root, int left_bound, int right_bound, int query_left,
int query_right) const {
if (root == 0 || query_right <= left_bound || right_bound <= query_left) {
return Count{};
}
if (query_left <= left_bound && right_bound <= query_right) {
return nodes[root].sum;
}
int middle = std::midpoint(left_bound, right_bound);
return count_impl(nodes[root].left, left_bound, middle, query_left,
query_right) +
count_impl(nodes[root].right, middle, right_bound, query_left,
query_right);
}
int extract_impl(int &root, int left_bound, int right_bound, int query_left,
int query_right) {
if (root == 0 || query_right <= left_bound || right_bound <= query_left) {
return 0;
}
if (query_left <= left_bound && right_bound <= query_right) {
int result = root;
root = 0;
return result;
}
int result = make_node();
int middle = std::midpoint(left_bound, right_bound);
int left_child = nodes[root].left;
int right_child = nodes[root].right;
nodes[result].left = extract_impl(left_child, left_bound, middle,
query_left, query_right);
nodes[result].right = extract_impl(right_child, middle, right_bound,
query_left, query_right);
nodes[root].left = left_child;
nodes[root].right = right_child;
pull(root);
pull(result);
if (nodes[result].sum == Count{}) {
return 0;
}
return result;
}
int merge_impl(int destination, int source) {
if (destination == 0 || source == 0) {
return destination | source;
}
int destination_left = nodes[destination].left;
int destination_right = nodes[destination].right;
destination_left = merge_impl(destination_left, nodes[source].left);
destination_right = merge_impl(destination_right, nodes[source].right);
nodes[destination].left = destination_left;
nodes[destination].right = destination_right;
if (destination_left == 0 && destination_right == 0) {
nodes[destination].sum += nodes[source].sum;
} else {
pull(destination);
}
return destination;
}
};
} // namespace noya
#endif // NOYA_MERGEABLE_FREQUENCY_TREE_HPP
#include <cassert>
#include <numeric>
#include <vector>
/// @complexity Time: O(log U) update/query; O(min(nodes_a,nodes_b)) destructive merge.
/// Space: O(number of allocated nodes).
namespace noya {
/// @brief Dynamic frequency segment-tree pool supporting point updates, rank
/// queries, destructive merging, and interval extraction in O(log U).
template <class Count = int> struct mergeable_frequency_tree {
struct node {
int left = 0;
int right = 0;
Count sum{};
};
int lower = 0;
int upper = 0;
std::vector<node> nodes{{}};
mergeable_frequency_tree() = default;
mergeable_frequency_tree(int lower_bound, int upper_bound)
: lower(lower_bound), upper(upper_bound) {
assert(lower < upper);
}
Count total(int root) const {
check_root(root);
return nodes[root].sum;
}
/// @brief Add delta at position, creating root and path nodes as needed.
void add(int &root, int position, Count delta) {
assert(lower <= position && position < upper);
add_impl(root, lower, upper, position, delta);
}
/// @brief Return the total frequency in [query_left, query_right).
Count count(int root, int query_left, int query_right) const {
check_root(root);
assert(lower <= query_left && query_left <= query_right &&
query_right <= upper);
return count_impl(root, lower, upper, query_left, query_right);
}
/// @brief Return the coordinate containing zero-indexed rank k.
int kth(int root, Count k) const {
check_root(root);
assert(Count{} <= k && k < nodes[root].sum);
int left_bound = lower;
int right_bound = upper;
while (right_bound - left_bound > 1) {
Count left_sum = nodes[nodes[root].left].sum;
int middle = std::midpoint(left_bound, right_bound);
if (k < left_sum) {
root = nodes[root].left;
right_bound = middle;
} else {
k -= left_sum;
root = nodes[root].right;
left_bound = middle;
}
}
return left_bound;
}
/// @brief Move every frequency in [query_left, query_right) from root into
/// a new root without duplicating leaves.
int extract(int &root, int query_left, int query_right) {
check_root(root);
assert(lower <= query_left && query_left <= query_right &&
query_right <= upper);
return extract_impl(root, lower, upper, query_left, query_right);
}
/// @brief Destructively merge source into destination and clear source.
void merge_into(int &destination, int &source) {
check_root(destination);
check_root(source);
if (destination == source && destination != 0) {
assert(false && "cannot merge a root into itself");
}
destination = merge_impl(destination, source);
source = 0;
}
private:
void check_root(int root) const {
assert(0 <= root && root < int(nodes.size()));
}
int make_node() {
nodes.push_back({});
return int(nodes.size()) - 1;
}
void pull(int root) {
nodes[root].sum =
nodes[nodes[root].left].sum + nodes[nodes[root].right].sum;
}
void add_impl(int &root, int left_bound, int right_bound, int position,
Count delta) {
if (root == 0) {
root = make_node();
}
if (right_bound - left_bound == 1) {
nodes[root].sum += delta;
assert(nodes[root].sum >= Count{});
return;
}
int middle = std::midpoint(left_bound, right_bound);
if (position < middle) {
int child = nodes[root].left;
add_impl(child, left_bound, middle, position, delta);
nodes[root].left = child;
} else {
int child = nodes[root].right;
add_impl(child, middle, right_bound, position, delta);
nodes[root].right = child;
}
pull(root);
}
Count count_impl(int root, int left_bound, int right_bound, int query_left,
int query_right) const {
if (root == 0 || query_right <= left_bound || right_bound <= query_left) {
return Count{};
}
if (query_left <= left_bound && right_bound <= query_right) {
return nodes[root].sum;
}
int middle = std::midpoint(left_bound, right_bound);
return count_impl(nodes[root].left, left_bound, middle, query_left,
query_right) +
count_impl(nodes[root].right, middle, right_bound, query_left,
query_right);
}
int extract_impl(int &root, int left_bound, int right_bound, int query_left,
int query_right) {
if (root == 0 || query_right <= left_bound || right_bound <= query_left) {
return 0;
}
if (query_left <= left_bound && right_bound <= query_right) {
int result = root;
root = 0;
return result;
}
int result = make_node();
int middle = std::midpoint(left_bound, right_bound);
int left_child = nodes[root].left;
int right_child = nodes[root].right;
nodes[result].left = extract_impl(left_child, left_bound, middle,
query_left, query_right);
nodes[result].right = extract_impl(right_child, middle, right_bound,
query_left, query_right);
nodes[root].left = left_child;
nodes[root].right = right_child;
pull(root);
pull(result);
if (nodes[result].sum == Count{}) {
return 0;
}
return result;
}
int merge_impl(int destination, int source) {
if (destination == 0 || source == 0) {
return destination | source;
}
int destination_left = nodes[destination].left;
int destination_right = nodes[destination].right;
destination_left = merge_impl(destination_left, nodes[source].left);
destination_right = merge_impl(destination_right, nodes[source].right);
nodes[destination].left = destination_left;
nodes[destination].right = destination_right;
if (destination_left == 0 && destination_right == 0) {
nodes[destination].sum += nodes[source].sum;
} else {
pull(destination);
}
return destination;
}
};
} // namespace noya