fractional_cascading.hpp¶
在多组有序表中连续查找同一个值，只做一次完整二分并沿预存指针传播位置。
Complexity: Time: \(O(N + k)\) build and \(O(\log (N + 1) + k)\) query for \(k\) sorted arrays containing \(N\) values in total. Space: \(O(N + k)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(N+k) build and O(log(N+1)+k) query for k sorted arrays
/// containing N values in total. Space: O(N+k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fractional cascading over sorted arrays: construct sampled catalogs
/// and answer all k lower bounds with one binary search and O(k) corrections.
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;
}
const std::vector<T> empty;
for (int idx = int(arr.size()) - 1; idx >= 0; --idx) {
bool has_next = idx + 1 < int(arr.size());
const auto &next = has_next ? lg[idx + 1].a : empty;
const auto &own = arr[idx];
auto &cur = lg[idx];
auto total = own.size() + next.size() / 2;
cur.a.reserve(total);
cur.ps.reserve(total + 1);
if (has_next)
cur.nxt.reserve(total + 1);
int pos = 0, sample = 1, down = 0;
while (pos < int(own.size()) || sample < int(next.size())) {
bool take_own = sample >= int(next.size()) ||
(pos < int(own.size()) && !cmp(next[sample], own[pos]));
const T &value = take_own ? own[pos] : next[sample];
// Equivalent values share their first lower-bound position.
int original = pos;
if (!cur.a.empty() && !cmp(cur.a.back(), value))
original = cur.ps.back();
cur.a.push_back(value);
cur.ps.push_back(original);
if (take_own)
++pos;
else
sample += 2;
if (has_next) {
while (down < int(next.size()) && cmp(next[down], value))
++down;
cur.nxt.push_back(down);
}
}
cur.ps.push_back(int(own.size()));
if (has_next)
cur.nxt.push_back(int(next.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
// NOYA_FRACTIONAL_CASCADING_HPP
#ifndef NOYA_FRACTIONAL_CASCADING_HPP
#define NOYA_FRACTIONAL_CASCADING_HPP 1
/// @complexity Time: O(N+k) build and O(log(N+1)+k) query for k sorted arrays
/// containing N values in total. Space: O(N+k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fractional cascading over sorted arrays: construct sampled catalogs
/// and answer all k lower bounds with one binary search and O(k) corrections.
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;
}
const std::vector<T> empty;
for (int idx = int(arr.size()) - 1; idx >= 0; --idx) {
bool has_next = idx + 1 < int(arr.size());
const auto &next = has_next ? lg[idx + 1].a : empty;
const auto &own = arr[idx];
auto &cur = lg[idx];
auto total = own.size() + next.size() / 2;
cur.a.reserve(total);
cur.ps.reserve(total + 1);
if (has_next)
cur.nxt.reserve(total + 1);
int pos = 0, sample = 1, down = 0;
while (pos < int(own.size()) || sample < int(next.size())) {
bool take_own = sample >= int(next.size()) ||
(pos < int(own.size()) && !cmp(next[sample], own[pos]));
const T &value = take_own ? own[pos] : next[sample];
// Equivalent values share their first lower-bound position.
int original = pos;
if (!cur.a.empty() && !cmp(cur.a.back(), value))
original = cur.ps.back();
cur.a.push_back(value);
cur.ps.push_back(original);
if (take_own)
++pos;
else
sample += 2;
if (has_next) {
while (down < int(next.size()) && cmp(next[down], value))
++down;
cur.nxt.push_back(down);
}
}
cur.ps.push_back(int(own.size()));
if (has_next)
cur.nxt.push_back(int(next.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
/// @complexity Time: O(N+k) build and O(log(N+1)+k) query for k sorted arrays
/// containing N values in total. Space: O(N+k).
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fractional cascading over sorted arrays: construct sampled catalogs
/// and answer all k lower bounds with one binary search and O(k) corrections.
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;
}
const std::vector<T> empty;
for (int idx = int(arr.size()) - 1; idx >= 0; --idx) {
bool has_next = idx + 1 < int(arr.size());
const auto &next = has_next ? lg[idx + 1].a : empty;
const auto &own = arr[idx];
auto &cur = lg[idx];
auto total = own.size() + next.size() / 2;
cur.a.reserve(total);
cur.ps.reserve(total + 1);
if (has_next)
cur.nxt.reserve(total + 1);
int pos = 0, sample = 1, down = 0;
while (pos < int(own.size()) || sample < int(next.size())) {
bool take_own = sample >= int(next.size()) ||
(pos < int(own.size()) && !cmp(next[sample], own[pos]));
const T &value = take_own ? own[pos] : next[sample];
// Equivalent values share their first lower-bound position.
int original = pos;
if (!cur.a.empty() && !cmp(cur.a.back(), value))
original = cur.ps.back();
cur.a.push_back(value);
cur.ps.push_back(original);
if (take_own)
++pos;
else
sample += 2;
if (has_next) {
while (down < int(next.size()) && cmp(next[down], value))
++down;
cur.nxt.push_back(down);
}
}
cur.ps.push_back(int(own.size()));
if (has_next)
cur.nxt.push_back(int(next.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
// NOYA_FRACTIONAL_CASCADING_HPP