fractional_cascading.hpp¶
在多组有序表中连续查找同一个值，只做一次完整二分并沿预存指针传播位置。
Complexity: Time: O(N) build over N stored elements and O(k + log N) across k arrays. Space: O(N).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(N) build over N stored elements and O(k + log N) across k arrays.
/// Space: O(N).
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fractional cascading over sorted arrays: O(N) construction and all
/// k lower bounds in O(log N + k) per query.
template <class T, class Compare = std::less<T>> struct fractional_cascading {
struct level {
std::vector<T> a;
std::vector<int> ps;
std::vector<int> nxt;
};
Compare cmp{};
std::vector<std::vector<T>> arr;
std::vector<level> lg;
fractional_cascading() = default;
explicit fractional_cascading(std::vector<std::vector<T>> A,
Compare cm0 = Compare{})
: cmp(std::move(cm0)) {
build(std::move(A));
}
void build(std::vector<std::vector<T>> A) {
arr = std::move(A);
for (const auto &val : arr) {
assert(std::is_sorted(val.begin(), val.end(), cmp));
}
lg.assign(arr.size(), {});
if (arr.empty()) {
return;
}
for (int idx = int(arr.size()) - 1; idx >= 0; idx--) {
std::vector<T> buf;
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
buf.reserve(nx0.size() / 2);
for (int pos = 1; pos < int(nx0.size()); pos += 2) {
buf.push_back(nx0[pos]);
}
}
auto &cur = lg[idx];
cur.a.reserve(arr[idx].size() + buf.size());
std::merge(arr[idx].begin(), arr[idx].end(), buf.begin(), buf.end(),
std::back_inserter(cur.a), cmp);
cur.ps.resize(cur.a.size() + 1);
int p0 = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (p0 < int(arr[idx].size()) && cmp(arr[idx][p0], cur.a[pos])) {
p0++;
}
cur.ps[pos] = p0;
}
cur.ps.back() = int(arr[idx].size());
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
cur.nxt.resize(cur.a.size() + 1);
int dn = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (dn < int(nx0.size()) && cmp(nx0[dn], cur.a[pos])) {
dn++;
}
cur.nxt[pos] = dn;
}
cur.nxt.back() = int(nx0.size());
}
}
}
/// @brief Return lower_bound indices for value in every original array.
std::vector<int> lower_bound_indices(const T &v) const {
if (lg.empty()) {
return {};
}
std::vector<int> res(lg.size());
int pos = int(std::lower_bound(lg[0].a.begin(), lg[0].a.end(), v, cmp) -
lg[0].a.begin());
for (int idx = 0; idx < int(lg.size()); idx++) {
res[idx] = lg[idx].ps[pos];
if (idx + 1 == int(lg.size())) {
break;
}
pos = lg[idx].nxt[pos];
if (pos > 0 && !cmp(lg[idx + 1].a[pos - 1], v)) {
pos--;
}
}
return res;
}
};
} // namespace noya
#ifndef NOYA_FRACTIONAL_CASCADING_HPP
#define NOYA_FRACTIONAL_CASCADING_HPP 1
/// @complexity Time: O(N) build over N stored elements and O(k + log N) across k arrays.
/// Space: O(N).
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fractional cascading over sorted arrays: O(N) construction and all
/// k lower bounds in O(log N + k) per query.
template <class T, class Compare = std::less<T>> struct fractional_cascading {
struct level {
std::vector<T> a;
std::vector<int> ps;
std::vector<int> nxt;
};
Compare cmp{};
std::vector<std::vector<T>> arr;
std::vector<level> lg;
fractional_cascading() = default;
explicit fractional_cascading(std::vector<std::vector<T>> A,
Compare cm0 = Compare{})
: cmp(std::move(cm0)) {
build(std::move(A));
}
void build(std::vector<std::vector<T>> A) {
arr = std::move(A);
for (const auto &val : arr) {
assert(std::is_sorted(val.begin(), val.end(), cmp));
}
lg.assign(arr.size(), {});
if (arr.empty()) {
return;
}
for (int idx = int(arr.size()) - 1; idx >= 0; idx--) {
std::vector<T> buf;
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
buf.reserve(nx0.size() / 2);
for (int pos = 1; pos < int(nx0.size()); pos += 2) {
buf.push_back(nx0[pos]);
}
}
auto &cur = lg[idx];
cur.a.reserve(arr[idx].size() + buf.size());
std::merge(arr[idx].begin(), arr[idx].end(), buf.begin(), buf.end(),
std::back_inserter(cur.a), cmp);
cur.ps.resize(cur.a.size() + 1);
int p0 = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (p0 < int(arr[idx].size()) && cmp(arr[idx][p0], cur.a[pos])) {
p0++;
}
cur.ps[pos] = p0;
}
cur.ps.back() = int(arr[idx].size());
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
cur.nxt.resize(cur.a.size() + 1);
int dn = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (dn < int(nx0.size()) && cmp(nx0[dn], cur.a[pos])) {
dn++;
}
cur.nxt[pos] = dn;
}
cur.nxt.back() = int(nx0.size());
}
}
}
/// @brief Return lower_bound indices for value in every original array.
std::vector<int> lower_bound_indices(const T &v) const {
if (lg.empty()) {
return {};
}
std::vector<int> res(lg.size());
int pos = int(std::lower_bound(lg[0].a.begin(), lg[0].a.end(), v, cmp) -
lg[0].a.begin());
for (int idx = 0; idx < int(lg.size()); idx++) {
res[idx] = lg[idx].ps[pos];
if (idx + 1 == int(lg.size())) {
break;
}
pos = lg[idx].nxt[pos];
if (pos > 0 && !cmp(lg[idx + 1].a[pos - 1], v)) {
pos--;
}
}
return res;
}
};
} // namespace noya
#endif // NOYA_FRACTIONAL_CASCADING_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
/// @complexity Time: O(N) build over N stored elements and O(k + log N) across k arrays.
/// Space: O(N).
namespace noya {
/// @brief Fractional cascading over sorted arrays: O(N) construction and all
/// k lower bounds in O(log N + k) per query.
template <class T, class Compare = std::less<T>> struct fractional_cascading {
struct level {
std::vector<T> a;
std::vector<int> ps;
std::vector<int> nxt;
};
Compare cmp{};
std::vector<std::vector<T>> arr;
std::vector<level> lg;
fractional_cascading() = default;
explicit fractional_cascading(std::vector<std::vector<T>> A,
Compare cm0 = Compare{})
: cmp(std::move(cm0)) {
build(std::move(A));
}
void build(std::vector<std::vector<T>> A) {
arr = std::move(A);
for (const auto &val : arr) {
assert(std::is_sorted(val.begin(), val.end(), cmp));
}
lg.assign(arr.size(), {});
if (arr.empty()) {
return;
}
for (int idx = int(arr.size()) - 1; idx >= 0; idx--) {
std::vector<T> buf;
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
buf.reserve(nx0.size() / 2);
for (int pos = 1; pos < int(nx0.size()); pos += 2) {
buf.push_back(nx0[pos]);
}
}
auto &cur = lg[idx];
cur.a.reserve(arr[idx].size() + buf.size());
std::merge(arr[idx].begin(), arr[idx].end(), buf.begin(), buf.end(),
std::back_inserter(cur.a), cmp);
cur.ps.resize(cur.a.size() + 1);
int p0 = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (p0 < int(arr[idx].size()) && cmp(arr[idx][p0], cur.a[pos])) {
p0++;
}
cur.ps[pos] = p0;
}
cur.ps.back() = int(arr[idx].size());
if (idx + 1 < int(arr.size())) {
const auto &nx0 = lg[idx + 1].a;
cur.nxt.resize(cur.a.size() + 1);
int dn = 0;
for (int pos = 0; pos < int(cur.a.size()); pos++) {
while (dn < int(nx0.size()) && cmp(nx0[dn], cur.a[pos])) {
dn++;
}
cur.nxt[pos] = dn;
}
cur.nxt.back() = int(nx0.size());
}
}
}
/// @brief Return lower_bound indices for value in every original array.
std::vector<int> lower_bound_indices(const T &v) const {
if (lg.empty()) {
return {};
}
std::vector<int> res(lg.size());
int pos = int(std::lower_bound(lg[0].a.begin(), lg[0].a.end(), v, cmp) -
lg[0].a.begin());
for (int idx = 0; idx < int(lg.size()); idx++) {
res[idx] = lg[idx].ps[pos];
if (idx + 1 == int(lg.size())) {
break;
}
pos = lg[idx].nxt[pos];
if (pos > 0 && !cmp(lg[idx + 1].a[pos - 1], v)) {
pos--;
}
}
return res;
}
};
} // namespace noya