description: Fractional cascading over sorted arrays: O(N) construction and all k lower bounds in O(log N + k) per query.¶

fractional_cascading.hpp¶

SECTIONData Structure INCLUDEnoya/fractional_cascading.hpp

Fractional cascading over sorted arrays: O(N) construction and all k lower bounds in O(log N + k) per query.

在多组有序表中连续查找同一个值，只做一次完整二分并沿预存指针传播位置。

Implementation¶

SourceExpanded

#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> values;
    std::vector<int> original_position;
    std::vector<int> next_position;
  };

  Compare compare{};
  std::vector<std::vector<T>> arrays;
  std::vector<level> levels;

  fractional_cascading() = default;
  explicit fractional_cascading(std::vector<std::vector<T>> sorted_arrays,
                                Compare compare_ = Compare{})
      : compare(std::move(compare_)) {
    build(std::move(sorted_arrays));
  }

  void build(std::vector<std::vector<T>> sorted_arrays) {
    arrays = std::move(sorted_arrays);
    for (const auto &array : arrays) {
      assert(std::is_sorted(array.begin(), array.end(), compare));
    }
    levels.assign(arrays.size(), {});
    if (arrays.empty()) {
      return;
    }
    for (int index = int(arrays.size()) - 1; index >= 0; index--) {
      std::vector<T> sampled;
      if (index + 1 < int(arrays.size())) {
        const auto &next = levels[index + 1].values;
        sampled.reserve(next.size() / 2);
        for (int position = 1; position < int(next.size()); position += 2) {
          sampled.push_back(next[position]);
        }
      }
      auto &current = levels[index];
      current.values.reserve(arrays[index].size() + sampled.size());
      std::merge(arrays[index].begin(), arrays[index].end(), sampled.begin(),
                 sampled.end(), std::back_inserter(current.values), compare);

      current.original_position.resize(current.values.size() + 1);
      int original = 0;
      for (int position = 0; position < int(current.values.size()); position++) {
        while (original < int(arrays[index].size()) &&
               compare(arrays[index][original], current.values[position])) {
          original++;
        }
        current.original_position[position] = original;
      }
      current.original_position.back() = int(arrays[index].size());

      if (index + 1 < int(arrays.size())) {
        const auto &next = levels[index + 1].values;
        current.next_position.resize(current.values.size() + 1);
        int down = 0;
        for (int position = 0; position < int(current.values.size());
             position++) {
          while (down < int(next.size()) &&
                 compare(next[down], current.values[position])) {
            down++;
          }
          current.next_position[position] = down;
        }
        current.next_position.back() = int(next.size());
      }
    }
  }

  /// @brief Return lower_bound indices for value in every original array.
  std::vector<int> lower_bound_indices(const T &value) const {
    if (levels.empty()) {
      return {};
    }
    std::vector<int> result(levels.size());
    int position = int(std::lower_bound(levels[0].values.begin(),
                                        levels[0].values.end(), value, compare) -
                       levels[0].values.begin());
    for (int index = 0; index < int(levels.size()); index++) {
      result[index] = levels[index].original_position[position];
      if (index + 1 == int(levels.size())) {
        break;
      }
      position = levels[index].next_position[position];
      if (position > 0 &&
          !compare(levels[index + 1].values[position - 1], value)) {
        position--;
      }
    }
    return result;
  }
};

} // 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> values;
    std::vector<int> original_position;
    std::vector<int> next_position;
  };

  Compare compare{};
  std::vector<std::vector<T>> arrays;
  std::vector<level> levels;

  fractional_cascading() = default;
  explicit fractional_cascading(std::vector<std::vector<T>> sorted_arrays,
                                Compare compare_ = Compare{})
      : compare(std::move(compare_)) {
    build(std::move(sorted_arrays));
  }

  void build(std::vector<std::vector<T>> sorted_arrays) {
    arrays = std::move(sorted_arrays);
    for (const auto &array : arrays) {
      assert(std::is_sorted(array.begin(), array.end(), compare));
    }
    levels.assign(arrays.size(), {});
    if (arrays.empty()) {
      return;
    }
    for (int index = int(arrays.size()) - 1; index >= 0; index--) {
      std::vector<T> sampled;
      if (index + 1 < int(arrays.size())) {
        const auto &next = levels[index + 1].values;
        sampled.reserve(next.size() / 2);
        for (int position = 1; position < int(next.size()); position += 2) {
          sampled.push_back(next[position]);
        }
      }
      auto &current = levels[index];
      current.values.reserve(arrays[index].size() + sampled.size());
      std::merge(arrays[index].begin(), arrays[index].end(), sampled.begin(),
                 sampled.end(), std::back_inserter(current.values), compare);

      current.original_position.resize(current.values.size() + 1);
      int original = 0;
      for (int position = 0; position < int(current.values.size()); position++) {
        while (original < int(arrays[index].size()) &&
               compare(arrays[index][original], current.values[position])) {
          original++;
        }
        current.original_position[position] = original;
      }
      current.original_position.back() = int(arrays[index].size());

      if (index + 1 < int(arrays.size())) {
        const auto &next = levels[index + 1].values;
        current.next_position.resize(current.values.size() + 1);
        int down = 0;
        for (int position = 0; position < int(current.values.size());
             position++) {
          while (down < int(next.size()) &&
                 compare(next[down], current.values[position])) {
            down++;
          }
          current.next_position[position] = down;
        }
        current.next_position.back() = int(next.size());
      }
    }
  }

  /// @brief Return lower_bound indices for value in every original array.
  std::vector<int> lower_bound_indices(const T &value) const {
    if (levels.empty()) {
      return {};
    }
    std::vector<int> result(levels.size());
    int position = int(std::lower_bound(levels[0].values.begin(),
                                        levels[0].values.end(), value, compare) -
                       levels[0].values.begin());
    for (int index = 0; index < int(levels.size()); index++) {
      result[index] = levels[index].original_position[position];
      if (index + 1 == int(levels.size())) {
        break;
      }
      position = levels[index].next_position[position];
      if (position > 0 &&
          !compare(levels[index + 1].values[position - 1], value)) {
        position--;
      }
    }
    return result;
  }
};

} // namespace noya