persistent_order_statistics.hpp¶
保留数组各前缀的历史版本，并回答区间第 \(k\) 小或值域计数；适合静态区间顺序统计。
Complexity: Time: \(O(n \log (n + 1))\) build and \(O(\log (\sigma + 1))\) per query. Space: \(O(1 + n \log (\sigma + 1))\), where \(\sigma\) is the number of distinct values.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log(n+1)) build and O(log(sigma+1)) per query.
/// Space: O(1 + n log(sigma+1)), where sigma is the number of distinct values.
#include <algorithm>
#include <bit>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Persistent frequency segment tree for range kth and rank queries.
template <class T> struct persistent_order_statistics {
struct node {
int ls = 0;
int rs = 0;
int cnt = 0;
};
int n = 0;
std::vector<T> xs;
std::vector<node> tr{{}};
std::vector<int> rt{0};
persistent_order_statistics() = default;
explicit persistent_order_statistics(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
xs = a;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
tr.assign(1, {});
rt.assign(a.size() + 1, 0);
if (n > 0) {
tr.reserve(1 + a.size() * (1 + std::bit_width(xs.size() - 1)));
}
for (int idx = 0; idx < n; idx++) {
int pos =
int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
rt[idx + 1] = insert(rt[idx], 0, int(xs.size()), pos);
}
}
/// @brief Return the zero-indexed kth smallest value in [l, r).
T kth(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k < r - l);
int low = 0;
int hi = int(xs.size());
int rl = rt[l];
int rr = rt[r];
while (hi - low > 1) {
int mid = std::midpoint(low, hi);
int cl = tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt;
if (k < cl) {
rl = tr[rl].ls;
rr = tr[rr].ls;
hi = mid;
} else {
k -= cl;
rl = tr[rl].rs;
rr = tr[rr].rs;
low = mid;
}
}
return xs[low];
}
/// @brief Count values smaller than bound in [l, r).
int count_less(int l, int r, const T &lim) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[l], rt[r], 0, int(xs.size()), pos);
}
/// @brief Count values in [lo, big) within positions [l, r).
int count(int l, int r, const T &lo, const T &big) const {
return count_less(l, r, big) - count_less(l, r, lo);
}
private:
int insert(int rt0, int low, int hi, int pos) {
int cur = int(tr.size());
tr.push_back(tr[rt0]);
tr[cur].cnt++;
if (hi - low == 1) {
return cur;
}
int mid = std::midpoint(low, hi);
if (pos < mid) {
tr[cur].ls = insert(tr[rt0].ls, low, mid, pos);
} else {
tr[cur].rs = insert(tr[rt0].rs, mid, hi, pos);
}
return cur;
}
int prefix_count(int rl, int rr, int low, int hi, int r) const {
if (rl == rr || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rr].cnt - tr[rl].cnt;
}
int mid = std::midpoint(low, hi);
if (r <= mid) {
return prefix_count(tr[rl].ls, tr[rr].ls, low, mid, r);
}
return tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt +
prefix_count(tr[rl].rs, tr[rr].rs, mid, hi, r);
}
};
} // namespace noya
// NOYA_PERSISTENT_ORDER_STATISTICS_HPP
#ifndef NOYA_PERSISTENT_ORDER_STATISTICS_HPP
#define NOYA_PERSISTENT_ORDER_STATISTICS_HPP 1
/// @complexity Time: O(n log(n+1)) build and O(log(sigma+1)) per query.
/// Space: O(1 + n log(sigma+1)), where sigma is the number of distinct values.
#include <algorithm>
#include <bit>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Persistent frequency segment tree for range kth and rank queries.
template <class T> struct persistent_order_statistics {
struct node {
int ls = 0;
int rs = 0;
int cnt = 0;
};
int n = 0;
std::vector<T> xs;
std::vector<node> tr{{}};
std::vector<int> rt{0};
persistent_order_statistics() = default;
explicit persistent_order_statistics(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
xs = a;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
tr.assign(1, {});
rt.assign(a.size() + 1, 0);
if (n > 0) {
tr.reserve(1 + a.size() * (1 + std::bit_width(xs.size() - 1)));
}
for (int idx = 0; idx < n; idx++) {
int pos =
int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
rt[idx + 1] = insert(rt[idx], 0, int(xs.size()), pos);
}
}
/// @brief Return the zero-indexed kth smallest value in [l, r).
T kth(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k < r - l);
int low = 0;
int hi = int(xs.size());
int rl = rt[l];
int rr = rt[r];
while (hi - low > 1) {
int mid = std::midpoint(low, hi);
int cl = tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt;
if (k < cl) {
rl = tr[rl].ls;
rr = tr[rr].ls;
hi = mid;
} else {
k -= cl;
rl = tr[rl].rs;
rr = tr[rr].rs;
low = mid;
}
}
return xs[low];
}
/// @brief Count values smaller than bound in [l, r).
int count_less(int l, int r, const T &lim) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[l], rt[r], 0, int(xs.size()), pos);
}
/// @brief Count values in [lo, big) within positions [l, r).
int count(int l, int r, const T &lo, const T &big) const {
return count_less(l, r, big) - count_less(l, r, lo);
}
private:
int insert(int rt0, int low, int hi, int pos) {
int cur = int(tr.size());
tr.push_back(tr[rt0]);
tr[cur].cnt++;
if (hi - low == 1) {
return cur;
}
int mid = std::midpoint(low, hi);
if (pos < mid) {
tr[cur].ls = insert(tr[rt0].ls, low, mid, pos);
} else {
tr[cur].rs = insert(tr[rt0].rs, mid, hi, pos);
}
return cur;
}
int prefix_count(int rl, int rr, int low, int hi, int r) const {
if (rl == rr || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rr].cnt - tr[rl].cnt;
}
int mid = std::midpoint(low, hi);
if (r <= mid) {
return prefix_count(tr[rl].ls, tr[rr].ls, low, mid, r);
}
return tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt +
prefix_count(tr[rl].rs, tr[rr].rs, mid, hi, r);
}
};
} // namespace noya
#endif // NOYA_PERSISTENT_ORDER_STATISTICS_HPP
/// @complexity Time: O(n log(n+1)) build and O(log(sigma+1)) per query.
/// Space: O(1 + n log(sigma+1)), where sigma is the number of distinct values.
#include <algorithm>
#include <bit>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Persistent frequency segment tree for range kth and rank queries.
template <class T> struct persistent_order_statistics {
struct node {
int ls = 0;
int rs = 0;
int cnt = 0;
};
int n = 0;
std::vector<T> xs;
std::vector<node> tr{{}};
std::vector<int> rt{0};
persistent_order_statistics() = default;
explicit persistent_order_statistics(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
xs = a;
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
tr.assign(1, {});
rt.assign(a.size() + 1, 0);
if (n > 0) {
tr.reserve(1 + a.size() * (1 + std::bit_width(xs.size() - 1)));
}
for (int idx = 0; idx < n; idx++) {
int pos =
int(std::lower_bound(xs.begin(), xs.end(), a[idx]) - xs.begin());
rt[idx + 1] = insert(rt[idx], 0, int(xs.size()), pos);
}
}
/// @brief Return the zero-indexed kth smallest value in [l, r).
T kth(int l, int r, int k) const {
assert(0 <= l && l <= r && r <= n);
assert(0 <= k && k < r - l);
int low = 0;
int hi = int(xs.size());
int rl = rt[l];
int rr = rt[r];
while (hi - low > 1) {
int mid = std::midpoint(low, hi);
int cl = tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt;
if (k < cl) {
rl = tr[rl].ls;
rr = tr[rr].ls;
hi = mid;
} else {
k -= cl;
rl = tr[rl].rs;
rr = tr[rr].rs;
low = mid;
}
}
return xs[low];
}
/// @brief Count values smaller than bound in [l, r).
int count_less(int l, int r, const T &lim) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[l], rt[r], 0, int(xs.size()), pos);
}
/// @brief Count values in [lo, big) within positions [l, r).
int count(int l, int r, const T &lo, const T &big) const {
return count_less(l, r, big) - count_less(l, r, lo);
}
private:
int insert(int rt0, int low, int hi, int pos) {
int cur = int(tr.size());
tr.push_back(tr[rt0]);
tr[cur].cnt++;
if (hi - low == 1) {
return cur;
}
int mid = std::midpoint(low, hi);
if (pos < mid) {
tr[cur].ls = insert(tr[rt0].ls, low, mid, pos);
} else {
tr[cur].rs = insert(tr[rt0].rs, mid, hi, pos);
}
return cur;
}
int prefix_count(int rl, int rr, int low, int hi, int r) const {
if (rl == rr || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rr].cnt - tr[rl].cnt;
}
int mid = std::midpoint(low, hi);
if (r <= mid) {
return prefix_count(tr[rl].ls, tr[rr].ls, low, mid, r);
}
return tr[tr[rr].ls].cnt - tr[tr[rl].ls].cnt +
prefix_count(tr[rl].rs, tr[rr].rs, mid, hi, r);
}
};
} // namespace noya
// NOYA_PERSISTENT_ORDER_STATISTICS_HPP