Static Threshold Search

data_structure/static_threshold_search.hpp · GitHub で見る

共通ページ

固定した整数列で、閾値を満たす最初・最後の添字を検索します。標準の next_ge(l,x) は l <= i かつ A[i] >= x を満たす最小の i を返します。比較条件・検索方向を型で選びます。

#include "lib/data_structure/static_threshold_search.hpp"
#include <cassert>
#include <vector>

int main() {
	std::vector<int> a{2, 7, 1, 7, 4};
	StaticThresholdSearch<int> above(a);
	assert(above.next_ge(2, 6) == 3);
	assert(above.next_gt(0, 7) == above.size());
	assert(above.first(0, 3, 6) == 1);
	assert(above.next_record(0) == 1);

	StaticThresholdSearch<int, true> below(a);
	assert(below.next_le(1, 2) == 2);
	assert(below.next_lt(0, 2) == 2);

	StaticThresholdSearch<int, false, true> previous(a);
	assert(previous.prev_ge(4, 7) == 3);
	assert(previous.last(0, 3, 7) == 1);
}

型は StaticThresholdSearch<T = std::int64_t, bool Smaller = false, bool Reverse = false> です。T は bool を除く 64 bit 以下の標準整数型で、長さは INT_MAX 以下とします。符号付き・符号なしの最小値・最大値も使えます。閾値は同じ T を渡し、厳密不等号を実現するために x+1・x-1 は計算しません。

型引数	条件・方向
Smaller = false	A[i] >= x、strict 版は A[i] > x
Smaller = true	A[i] <= x、strict 版は A[i] < x
Reverse = false	指定位置以降の最小の添字
Reverse = true	指定端点より前の最大の添字

API	引数と返り値
StaticThresholdSearch()	空の索引
StaticThresholdSearch(std::vector<T> values)	列を値で受け取り保持する。lvalue はコピー、rvalue は領域を移す
build(std::vector<T> values)	列を置き換えて再構築。void
size() / empty()	列長を int / 空かを bool で返す
values() / operator[](int i)	元の順序の列を std::span<const T> / 要素を const T& で返す
clear() / swap(other)	空にする / 内容を交換する。void
next(l,x) / next_strict(l,x)	Reverse=false で使用。[l,size()) 内の条件を満たす最小の添字を int で返す
first(l,r,x) / first_strict(l,r,x)	Reverse=false で使用。[l,r) 内の最小の添字を int で返す
prev(r,x) / prev_strict(r,x)	Reverse=true で使用。[0,r) 内の条件を満たす最大の添字を int で返す
last(l,r,x) / last_strict(l,r,x)	Reverse=true で使用。[l,r) 内の最大の添字を int で返す
next_ge(l,x) / next_gt(l,x)	Smaller=false, Reverse=false の非 strict / strict 検索の別名
next_le(l,x) / next_lt(l,x)	Smaller=true, Reverse=false の非 strict / strict 検索の別名
prev_ge(r,x) / prev_gt(r,x)	Smaller=false, Reverse=true の非 strict / strict 検索の別名
prev_le(r,x) / prev_lt(r,x)	Smaller=true, Reverse=true の非 strict / strict 検索の別名
next_record(int i)	i より検索方向へ進んだ位置で、A[i] より厳密に良い値を持つ最も近い添字を int で返す。greater なら大きい値、smaller なら小さい値

すべての検索で、不在時は size() を返します。空の索引では結果は 0 です。重複値を含んでいても添字の最小・最大で決まります。prev の r は含まない端点なので、i <= p から探すには prev_ge(p+1,x) などを使います。引数の既定値は型引数だけです。

要素取得と next_record には 0 <= i < size()、1端点の検索には 0 <= l,r <= size()、区間検索には 0 <= l <= r <= size() を渡します。空区間の検索結果も size() です。型引数と異なる方向・条件のメソッドは使用できず、コンパイル時に検査します。

構築後は読み取り専用です。値の変更には build を使います。元の列を変更・破棄しても影響しません。build・clear・代入・破棄後は以前の参照や span を使わないでください。コピーは独立し、ムーブ元は空です。ムーブ・swap は noexcept。build の領域確保失敗時は元の索引を維持します。

列を 64 要素ずつのブロックに分け、ブロックごとの最小値・最大値を持つ木を構築します。検索開始位置を含むブロックは直接調べ、見つからなければ木をたどって条件を満たす最初・最後のブロックを探します。最後にそのブロック内を調べます。ハッシュや乱数は使いません。

列長を \(n\) とすると、構築は \(O(n)\) 時間、保持空間・構築時の空間は \(O(n)\) です。検索と next_record は最悪 \(O(\log n)\) 時間、追加空間 \(O(1)\) です。ブロック内の走査は固定長なので定数時間です。

サイズ・要素・列の取得・swap は \(O(1)\)、コピーと旧領域の解放は \(O(n)\)、ムーブ構築は \(O(1)\) です。空区間・長さ 0・1 の処理は定数時間です。

検証コード

• test/static_threshold_search.test.cpp

コード

#ifndef STATIC_THRESHOLD_SEARCH_HPP
#define STATIC_THRESHOLD_SEARCH_HPP

#include <algorithm>
#include <bit>
#include <cassert>
#include <concepts>
#include <cstdint>
#include <limits>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>

template <std::integral T = std::int64_t, bool Smaller = false, bool Reverse = false>
requires (sizeof(T) <= 8 && !std::is_same_v<T, bool>)
class StaticThresholdSearch {
	std::vector<T> values_, minimum_, maximum_;
	unsigned base_ = 1;
	enum class Mode { ge, gt, le, lt };
	template <Mode M> static bool accepts(T a, T x) {
		if constexpr (M == Mode::ge) return a >= x;
		if constexpr (M == Mode::gt) return a > x;
		if constexpr (M == Mode::le) return a <= x;
		if constexpr (M == Mode::lt) return a < x;
	}
	template <Mode M> const std::vector<T> &extrema() const {
		if constexpr (M == Mode::ge || M == Mode::gt) return maximum_;
		else return minimum_;
	}
	template <Mode M, bool Forward> int search(int endpoint, T x) const {
		assert(0 <= endpoint && endpoint <= size());
		if constexpr (Forward) { if (endpoint == size()) return size(); }
		else if (!endpoint) return size();
		int p = Forward ? endpoint : endpoint - 1;
		if (accepts<M>(values_[p], x)) return p;
		const auto &tree = extrema<M>();
		if (!accepts<M>(tree[1], x)) return size();
		unsigned block = unsigned(p) / 64;
		if constexpr (Forward) {
			int end = int(std::min<std::size_t>(values_.size(), std::size_t(block + 1) * 64));
			for (++p; p < end; ++p) if (accepts<M>(values_[p], x)) return p;
			unsigned k = base_ + block + 1;
			if (k == base_ * 2) return size();
			do {
				while (!(k & 1)) k >>= 1;
				if (accepts<M>(tree[k], x)) {
					while (k < base_) { k *= 2; if (!accepts<M>(tree[k], x)) ++k; }
					std::size_t begin = std::size_t(k - base_) * 64;
					end = int(std::min(values_.size(), begin + 64));
					for (std::size_t i = begin; i < std::size_t(end); ++i) if (accepts<M>(values_[i], x)) return int(i);
					return size();
				}
				++k;
			} while ((k & -k) != k);
		} else {
			int begin = int(block * 64);
			for (--p; p >= begin; --p) if (accepts<M>(values_[p], x)) return p;
			unsigned k = base_ + block;
			if (k == base_) return size();
			do {
				--k;
				while (k > 1 && (k & 1)) k >>= 1;
				if (accepts<M>(tree[k], x)) {
					while (k < base_) { k = k * 2 + 1; if (!accepts<M>(tree[k], x)) --k; }
					int last = int(std::min(values_.size(), std::size_t(k - base_ + 1) * 64));
					begin = int((k - base_) * 64);
					for (int i = last; i-- > begin;) if (accepts<M>(values_[i], x)) return i;
					return size();
				}
			} while ((k & -k) != k);
		}
		return size();
	}
	void check_range([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= size()); }
  public:
	StaticThresholdSearch() = default;
	explicit StaticThresholdSearch(std::vector<T> values) { build(std::move(values)); }
	StaticThresholdSearch(const StaticThresholdSearch &) = default;
	StaticThresholdSearch &operator=(const StaticThresholdSearch &other) {
		if (this != &other) { StaticThresholdSearch copy(other); swap(copy); } return *this;
	}
	StaticThresholdSearch(StaticThresholdSearch &&other) noexcept { swap(other); }
	StaticThresholdSearch &operator=(StaticThresholdSearch &&other) noexcept {
		if (this != &other) { StaticThresholdSearch moved(std::move(other)); swap(moved); } return *this;
	}
	void swap(StaticThresholdSearch &other) noexcept {
		values_.swap(other.values_); minimum_.swap(other.minimum_); maximum_.swap(other.maximum_); std::swap(base_, other.base_);
	}
	void build(std::vector<T> values) {
		assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
		StaticThresholdSearch next;
		next.values_ = std::move(values);
		unsigned blocks = unsigned((next.values_.size() + 63) / 64);
		next.base_ = std::bit_ceil(std::max(1U, blocks));
		next.minimum_.assign(std::size_t(next.base_) * 2, std::numeric_limits<T>::max());
		next.maximum_.assign(std::size_t(next.base_) * 2, std::numeric_limits<T>::lowest());
		for (std::size_t i = 0; i < next.values_.size(); ++i) {
			unsigned v = next.base_ + unsigned(i / 64);
			next.minimum_[v] = std::min(next.minimum_[v], next.values_[i]);
			next.maximum_[v] = std::max(next.maximum_[v], next.values_[i]);
		}
		for (unsigned v = next.base_ - 1; v; --v) {
			next.minimum_[v] = std::min(next.minimum_[v * 2], next.minimum_[v * 2 + 1]);
			next.maximum_[v] = std::max(next.maximum_[v * 2], next.maximum_[v * 2 + 1]);
		}
		swap(next);
	}
	void clear() { StaticThresholdSearch next; swap(next); }
	int size() const { return int(values_.size()); }
	bool empty() const { return values_.empty(); }
	std::span<const T> values() const { return values_; }
	const T &operator[](int i) const { assert(0 <= i && i < size()); return values_[i]; }
	int next(int l, T x) const requires (!Reverse) { return search<Smaller ? Mode::le : Mode::ge, true>(l, x); }
	int next_strict(int l, T x) const requires (!Reverse) { return search<Smaller ? Mode::lt : Mode::gt, true>(l, x); }
	int first(int l, int r, T x) const requires (!Reverse) { check_range(l, r); if (l == r) return size(); int p = next(l, x); return p < r ? p : size(); }
	int first_strict(int l, int r, T x) const requires (!Reverse) { check_range(l, r); if (l == r) return size(); int p = next_strict(l, x); return p < r ? p : size(); }
	int next_ge(int l, T x) const requires (!Smaller && !Reverse) { return next(l, x); }
	int next_gt(int l, T x) const requires (!Smaller && !Reverse) { return next_strict(l, x); }
	int next_le(int l, T x) const requires (Smaller && !Reverse) { return next(l, x); }
	int next_lt(int l, T x) const requires (Smaller && !Reverse) { return next_strict(l, x); }
	int prev(int r, T x) const requires Reverse { return search<Smaller ? Mode::le : Mode::ge, false>(r, x); }
	int prev_strict(int r, T x) const requires Reverse { return search<Smaller ? Mode::lt : Mode::gt, false>(r, x); }
	int last(int l, int r, T x) const requires Reverse { check_range(l, r); if (l == r) return size(); int p = prev(r, x); return p != size() && p >= l ? p : size(); }
	int last_strict(int l, int r, T x) const requires Reverse { check_range(l, r); if (l == r) return size(); int p = prev_strict(r, x); return p != size() && p >= l ? p : size(); }
	int prev_ge(int r, T x) const requires (!Smaller && Reverse) { return prev(r, x); }
	int prev_gt(int r, T x) const requires (!Smaller && Reverse) { return prev_strict(r, x); }
	int prev_le(int r, T x) const requires (Smaller && Reverse) { return prev(r, x); }
	int prev_lt(int r, T x) const requires (Smaller && Reverse) { return prev_strict(r, x); }
	int next_record(int i) const {
		assert(0 <= i && i < size());
		if constexpr (Reverse) return search<Smaller ? Mode::lt : Mode::gt, false>(i, values_[i]);
		else return search<Smaller ? Mode::lt : Mode::gt, true>(i + 1, values_[i]);
	}
};

#endif

Back to top page