persistent_order_statistics.hpp¶
Persistent frequency segment tree for range kth and rank queries; build O(n log n), each query O(log n).
保留数组各前缀的历史版本，并回答区间第 k 小或值域计数；适合静态区间顺序统计。
Implementation¶
#ifndef NOYA_PERSISTENT_ORDER_STATISTICS_HPP
#define NOYA_PERSISTENT_ORDER_STATISTICS_HPP 1
/// @complexity Time: O(n log sigma) build and O(log sigma) per query.
/// Space: O(n log sigma).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Persistent frequency segment tree for range kth and rank queries;
/// build O(n log n), each query O(log n).
template <class T> struct persistent_order_statistics {
struct node {
int left = 0;
int right = 0;
int count = 0;
};
int n = 0;
std::vector<T> coordinates;
std::vector<node> nodes{{}};
std::vector<int> roots{0};
persistent_order_statistics() = default;
explicit persistent_order_statistics(const std::vector<T> &values) {
build(values);
}
void build(const std::vector<T> &values) {
n = int(values.size());
coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
nodes.assign(1, {});
roots.assign(n + 1, 0);
for (int index = 0; index < n; index++) {
int position = int(std::lower_bound(coordinates.begin(),
coordinates.end(), values[index]) -
coordinates.begin());
roots[index + 1] =
insert(roots[index], 0, int(coordinates.size()), position);
}
}
/// @brief Return the zero-indexed kth smallest value in [left, right).
T kth(int left, int right, int k) const {
assert(0 <= left && left <= right && right <= n);
assert(0 <= k && k < right - left);
int low = 0;
int high = int(coordinates.size());
int before_root = roots[left];
int after_root = roots[right];
while (high - low > 1) {
int middle = std::midpoint(low, high);
int left_count = nodes[nodes[after_root].left].count -
nodes[nodes[before_root].left].count;
if (k < left_count) {
before_root = nodes[before_root].left;
after_root = nodes[after_root].left;
high = middle;
} else {
k -= left_count;
before_root = nodes[before_root].right;
after_root = nodes[after_root].right;
low = middle;
}
}
return coordinates[low];
}
/// @brief Count values smaller than bound in [left, right).
int count_less(int left, int right, const T &bound) const {
assert(0 <= left && left <= right && right <= n);
int position =
int(std::lower_bound(coordinates.begin(), coordinates.end(), bound) -
coordinates.begin());
return prefix_count(roots[right], 0, int(coordinates.size()), position) -
prefix_count(roots[left], 0, int(coordinates.size()), position);
}
/// @brief Count values in [lower, upper) within positions [left, right).
int count(int left, int right, const T &lower, const T &upper) const {
return count_less(left, right, upper) - count_less(left, right, lower);
}
private:
int insert(int root, int low, int high, int position) {
int current = int(nodes.size());
nodes.push_back(nodes[root]);
nodes[current].count++;
if (high - low == 1) {
return current;
}
int middle = std::midpoint(low, high);
if (position < middle) {
nodes[current].left = insert(nodes[root].left, low, middle, position);
} else {
nodes[current].right = insert(nodes[root].right, middle, high, position);
}
return current;
}
int prefix_count(int root, int low, int high, int right) const {
if (root == 0 || right <= low) {
return 0;
}
if (high <= right) {
return nodes[root].count;
}
int middle = std::midpoint(low, high);
return prefix_count(nodes[root].left, low, middle, right) +
prefix_count(nodes[root].right, middle, high, right);
}
};
} // namespace noya
#endif // NOYA_PERSISTENT_ORDER_STATISTICS_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
/// @complexity Time: O(n log sigma) build and O(log sigma) per query.
/// Space: O(n log sigma).
namespace noya {
/// @brief Persistent frequency segment tree for range kth and rank queries;
/// build O(n log n), each query O(log n).
template <class T> struct persistent_order_statistics {
struct node {
int left = 0;
int right = 0;
int count = 0;
};
int n = 0;
std::vector<T> coordinates;
std::vector<node> nodes{{}};
std::vector<int> roots{0};
persistent_order_statistics() = default;
explicit persistent_order_statistics(const std::vector<T> &values) {
build(values);
}
void build(const std::vector<T> &values) {
n = int(values.size());
coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
nodes.assign(1, {});
roots.assign(n + 1, 0);
for (int index = 0; index < n; index++) {
int position = int(std::lower_bound(coordinates.begin(),
coordinates.end(), values[index]) -
coordinates.begin());
roots[index + 1] =
insert(roots[index], 0, int(coordinates.size()), position);
}
}
/// @brief Return the zero-indexed kth smallest value in [left, right).
T kth(int left, int right, int k) const {
assert(0 <= left && left <= right && right <= n);
assert(0 <= k && k < right - left);
int low = 0;
int high = int(coordinates.size());
int before_root = roots[left];
int after_root = roots[right];
while (high - low > 1) {
int middle = std::midpoint(low, high);
int left_count = nodes[nodes[after_root].left].count -
nodes[nodes[before_root].left].count;
if (k < left_count) {
before_root = nodes[before_root].left;
after_root = nodes[after_root].left;
high = middle;
} else {
k -= left_count;
before_root = nodes[before_root].right;
after_root = nodes[after_root].right;
low = middle;
}
}
return coordinates[low];
}
/// @brief Count values smaller than bound in [left, right).
int count_less(int left, int right, const T &bound) const {
assert(0 <= left && left <= right && right <= n);
int position =
int(std::lower_bound(coordinates.begin(), coordinates.end(), bound) -
coordinates.begin());
return prefix_count(roots[right], 0, int(coordinates.size()), position) -
prefix_count(roots[left], 0, int(coordinates.size()), position);
}
/// @brief Count values in [lower, upper) within positions [left, right).
int count(int left, int right, const T &lower, const T &upper) const {
return count_less(left, right, upper) - count_less(left, right, lower);
}
private:
int insert(int root, int low, int high, int position) {
int current = int(nodes.size());
nodes.push_back(nodes[root]);
nodes[current].count++;
if (high - low == 1) {
return current;
}
int middle = std::midpoint(low, high);
if (position < middle) {
nodes[current].left = insert(nodes[root].left, low, middle, position);
} else {
nodes[current].right = insert(nodes[root].right, middle, high, position);
}
return current;
}
int prefix_count(int root, int low, int high, int right) const {
if (root == 0 || right <= low) {
return 0;
}
if (high <= right) {
return nodes[root].count;
}
int middle = std::midpoint(low, high);
return prefix_count(nodes[root].left, low, middle, right) +
prefix_count(nodes[root].right, middle, high, right);
}
};
} // namespace noya