persistent_order_statistics.hpp¶
保留数组各前缀的历史版本，并回答区间第 \(k\) 小或值域计数；适合静态区间顺序统计。
Complexity: Time: O(n log sigma) build and O(log sigma) per query. Space: O(n log sigma).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 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(n + 1, 0);
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);
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[r], 0, int(xs.size()), pos) -
prefix_count(rt[l], 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 rt0, int low, int hi, int r) const {
if (rt0 == 0 || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rt0].cnt;
}
int mid = std::midpoint(low, hi);
return prefix_count(tr[rt0].ls, low, mid, r) +
prefix_count(tr[rt0].rs, mid, hi, r);
}
};
} // namespace noya
#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 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(n + 1, 0);
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);
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[r], 0, int(xs.size()), pos) -
prefix_count(rt[l], 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 rt0, int low, int hi, int r) const {
if (rt0 == 0 || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rt0].cnt;
}
int mid = std::midpoint(low, hi);
return prefix_count(tr[rt0].ls, low, mid, r) +
prefix_count(tr[rt0].rs, mid, hi, r);
}
};
} // 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 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(n + 1, 0);
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);
int pos = int(std::lower_bound(xs.begin(), xs.end(), lim) - xs.begin());
return prefix_count(rt[r], 0, int(xs.size()), pos) -
prefix_count(rt[l], 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 rt0, int low, int hi, int r) const {
if (rt0 == 0 || r <= low) {
return 0;
}
if (hi <= r) {
return tr[rt0].cnt;
}
int mid = std::midpoint(low, hi);
return prefix_count(tr[rt0].ls, low, mid, r) +
prefix_count(tr[rt0].rs, mid, hi, r);
}
};
} // namespace noya