Interval Set

data_structure/interval_set.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/interval_set.hpp"

IntervalSet<> s;
s.insert(2, 7);
s.insert(7, 10);
s.erase(4, 6);
auto size = s.size();       // 6
auto mex = s.mex(2);        // 4
auto next = s.next(5);      // 6
for (auto [l, r] : s) {}    // [2,4), [6,10)

整数の集合を、重ならず隣接もしない半開区間 \([l,r)\) に圧縮します。隣接する区間は自動で結合します。IntervalSet<T, Size> の T が座標型、Size が要素数の型です。T は bool を除く整数型で、__int128_t・__uint128_t や Boost.Multiprecision の整数型にも対応します。既定の座標型は std::int64_t です。

Size を省略すると、64 bit 以下の組み込み整数では std::uint64_t、128 bit の組み込み整数では __uint128_t、それ以外では T を使います。既存の IntervalSet<> の返り値は引き続き std::uint64_t です。T・Size は std::numeric_limits の is_integer が true になる型を使ってください。ヘッダー自体は Boost に依存しません。

#include <boost/multiprecision/cpp_int.hpp>
#include "lib/data_structure/interval_set.hpp"

IntervalSet<__int128_t> a;
__int128_t x = __int128_t(1) << 100;
a.insert(-x, x);
__uint128_t count = a.size();

using boost::multiprecision::cpp_int;
IntervalSet<cpp_int> b;
cpp_int y = cpp_int(1) << 1000;
b.insert(-y, y);
cpp_int large_count = b.size();

using boost::multiprecision::int256_t;
IntervalSet<int256_t, cpp_int> c;
c.insert((std::numeric_limits<int256_t>::lowest)(),
         (std::numeric_limits<int256_t>::max)());

Size では端点からの変換・長さの差・要素数の加減算を行います。これらを正確に計算できる型を選んでください。組み込み整数の既定型は座標型の全範囲に対応します。固定幅の多倍長整数では、座標が表せても要素数が収まらない場合があります。特に Boost の符号付き int256_t は、最小値から最大値までの長さが int256_t に収まりません。広い区間を扱う場合は、上の c のように Size に cpp_int を指定してください。IntervalSet<cpp_int> は座標・要素数ともに任意精度です。

区間の両端は T で表せる値で、\(l\le r\) が必要です。空区間の更新は何もしません。上限のある整数型では、右端も T で表すため、格納できる整数は T の最小値以上、最大値未満です。insert(x) は x が T の最大値未満の場合に使ってください。最大値を右端・検索座標に使うことはでき、erase(x) は最大値なら 0 を返します。cpp_int のように上限のない型では、この制限はありません。負の座標や、座標型の最小値と最大値にまたがる区間にも対応します。

next・prev は検索座標自身を含み、該当する要素がなければ std::nullopt を返します。mex(x) は \(x\) 以上で集合に含まれない最小の整数です。

操作	内容・返り値	計算量
IntervalSet()	空集合を作成	\(O(1)\)
IntervalSet(intervals)	vector<pair<T,T>> または初期化子リストの区間の和集合で初期化	\(O(m\log m+n)\)
IntervalSet(s) / s = t	コピー。区間も複製	\(O(n)\)
IntervalSet(std::move(s)) / s = std::move(t)	移動。移動元は空集合になる	構築: \(O(1)\)、代入: 移動先の区間数に比例
assign(intervals)	vector<pair<T,T>> の区間の和集合で置き換え。未ソート・重複・隣接を許す	\(O(m\log m+n)\)
insert(l,r) / insert(x)	区間／1 要素を追加。新しく増えた要素数を返す	区間: \(O(\log n+k)\)、単点: \(O(\log n)\)
erase(l,r) / erase(x)	区間／1 要素を削除。実際に減った要素数を返す	区間: \(O(\log n+k)\)、単点: \(O(\log n)\)
contains(x)	要素が含まれるか	\(O(\log n)\)
contains(l,r)	区間全体が含まれるか。空区間は true	\(O(\log n)\)
intersects(l,r)	区間に含まれる要素があるか。空区間は false	\(O(\log n)\)
count(l,r)	区間に含まれる要素数	\(O(\log n+k)\)
find(x)	x を含む区間のイテレータ。なければ end()	\(O(\log n)\)
lower_bound(x)	x を含む区間、なければ x より右にある最初の区間のイテレータ。なければ end()	\(O(\log n)\)
next(x) / prev(x)	x 以上の最小要素／x 以下の最大要素	\(O(\log n)\)
mex(x = 0)	x 以上の最小の非所属整数	\(O(\log n)\)
min() / max()	最小要素／最大要素。空集合は nullopt	\(O(1)\)
size()	集合の要素数	\(O(1)\)
interval_count()	圧縮後の区間数	\(O(1)\)
empty()	空集合か	\(O(1)\)
begin() / end()	区間を左端の昇順に走査する読み取り専用イテレータ	\(O(1)\)
rbegin() / rend()	区間を降順に走査する読み取り専用イテレータ	\(O(1)\)
clear()	空集合に戻す	\(O(n)\)
swap(t) / swap(s,t)	集合を交換	\(O(1)\)

coordinate_type は T、size_type は Size、interval_type は std::pair<T,T> です。insert・erase・count・size は size_type を返します。const_iterator・const_reverse_iterator の参照先は左端・右端の組です。更新時に結合・分割・削除・左端の変更を受けた区間のイテレータは使い直してください。構築にはソート後の挿入ヒント、更新には木のノードの再利用を使います。

操作前後の区間数の最大値を \(n\)、更新・列挙で触れる区間数を \(k\) として、insert・erase・count は \(O(\log n+k)\)、単点更新・検索・contains・intersects・find・lower_bound・next・prev・mex は \(O(\log n)\) です。長さ \(m\) の区間列からの構築・assign は \(O(m\log m+n)\)、コピー・clear は \(O(n)\) です。移動代入は移動先にあった区間数に比例します。それ以外の操作は \(O(1)\)、空間は \(O(n)\)、構築・assign 中は入力を含めて \(O(m+n)\) です。

上記は整数の比較・演算・コピー・交換を \(O(1)\) とした計算量です。多倍長整数では、使用する型と桁数に応じたコストが加わります。size() も要素数を値で返すため、多倍長整数ではそのコピーが発生します。

検証コード

• test/interval_set_predecessor.test.cpp

コード

#ifndef INTERVAL_SET_HPP
#define INTERVAL_SET_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <map>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template<class T = std::int64_t, class Size = std::conditional_t<
	std::is_integral_v<T> && sizeof(T) <= 8, std::uint64_t,
	std::conditional_t<std::is_same_v<T, __int128_t>, __uint128_t, T>>>
class IntervalSet {
	static_assert(std::numeric_limits<T>::is_integer && !std::is_same_v<T, bool>);
	static_assert(std::numeric_limits<Size>::is_integer && !std::is_same_v<Size, bool>);
	std::map<T, T> ranges;
	Size total = 0;
	static Size length(const T &l, const T &r) {
		return static_cast<Size>(r) - static_cast<Size>(l);
	}

public:
	using coordinate_type = T;
	using size_type = Size;
	using interval_type = std::pair<T, T>;
	using const_iterator = typename std::map<T, T>::const_iterator;
	using const_reverse_iterator = typename std::map<T, T>::const_reverse_iterator;

	IntervalSet() = default;
	explicit IntervalSet(std::vector<interval_type> intervals) { assign(std::move(intervals)); }
	IntervalSet(std::initializer_list<interval_type> intervals) { assign(intervals); }
	IntervalSet(const IntervalSet &) = default;
	IntervalSet(IntervalSet &&other) noexcept(std::is_nothrow_constructible_v<Size, int> && std::is_nothrow_swappable_v<Size>) { swap(other); }
	IntervalSet &operator=(IntervalSet other) noexcept(std::is_nothrow_swappable_v<Size>) { swap(other); return *this; }

	void assign(std::vector<interval_type> intervals) {
		std::sort(intervals.begin(), intervals.end());
		IntervalSet result;
		auto last = result.ranges.end();
		for (auto [l, r] : intervals) {
			assert(l <= r);
			if (l == r) continue;
			if (last != result.ranges.end() && l <= last->second) {
				if (last->second < r) {
					result.total += length(last->second, r);
					last->second = r;
				}
			} else {
				last = result.ranges.emplace_hint(result.ranges.end(), l, r);
				result.total += length(l, r);
			}
		}
		swap(result);
	}

	size_type insert(T l, T r) {
		assert(l <= r);
		if (l == r) return 0;
		auto it = ranges.upper_bound(l);
		if (it != ranges.begin() && std::prev(it)->second >= l) --it;
		if (it == ranges.end() || it->first > r) {
			ranges.emplace_hint(it, l, r);
			auto added = length(l, r);
			total += added;
			return added;
		}
		if (it->first <= l && r <= it->second) return 0;
		T left = (std::min)(l, it->first), right = (std::max)(r, it->second);
		auto removed = length(it->first, it->second);
		auto next_it = std::next(it);
		while (next_it != ranges.end() && next_it->first <= right) {
			right = (std::max)(right, next_it->second);
			removed += length(next_it->first, next_it->second);
			next_it = ranges.erase(next_it);
		}
		if (left == it->first) it->second = right;
		else {
			auto node = ranges.extract(it);
			node.key() = left;
			node.mapped() = right;
			ranges.insert(next_it, std::move(node));
		}
		size_type added = length(left, right) - removed;
		total += added;
		return added;
	}

	size_type insert(T x) {
		if constexpr (std::numeric_limits<T>::is_bounded) assert(x < (std::numeric_limits<T>::max)());
		return insert(x, static_cast<T>(x + 1));
	}

	size_type erase(T l, T r) {
		assert(l <= r);
		if (l == r) return 0;
		auto it = ranges.upper_bound(l);
		if (it != ranges.begin() && std::prev(it)->second > l) --it;
		size_type removed = 0;
		if (it != ranges.end() && it->first < l) {
			T right = it->second;
			if (r < right) {
				ranges.emplace_hint(std::next(it), r, right);
				it->second = l;
				removed = length(l, r);
				total -= removed;
				return removed;
			}
			removed = length(l, right);
			it->second = l;
			++it;
		}
		while (it != ranges.end() && it->first < r) {
			if (r < it->second) {
				removed += length(it->first, r);
				auto hint = std::next(it);
				auto node = ranges.extract(it);
				node.key() = r;
				ranges.insert(hint, std::move(node));
				break;
			}
			removed += length(it->first, it->second);
			it = ranges.erase(it);
		}
		total -= removed;
		return removed;
	}

	size_type erase(T x) {
		if constexpr (std::numeric_limits<T>::is_bounded)
			if (x == (std::numeric_limits<T>::max)()) return 0;
		return erase(x, static_cast<T>(x + 1));
	}

	const_iterator find(T x) const {
		auto it = ranges.upper_bound(x);
		if (it == ranges.begin()) return ranges.end();
		--it;
		return x < it->second ? it : ranges.end();
	}
	const_iterator lower_bound(T x) const {
		auto it = ranges.upper_bound(x);
		if (it != ranges.begin() && x < std::prev(it)->second) --it;
		return it;
	}
	bool contains(T x) const { return find(x) != end(); }
	bool contains(T l, T r) const {
		assert(l <= r);
		if (l == r) return true;
		auto it = find(l);
		return it != end() && r <= it->second;
	}
	bool intersects(T l, T r) const {
		assert(l <= r);
		if (l == r) return false;
		auto it = lower_bound(l);
		return it != end() && it->first < r;
	}
	size_type count(T l, T r) const {
		assert(l <= r);
		if (l == r) return 0;
		size_type result = 0;
		for (auto it = lower_bound(l); it != end() && it->first < r; ++it)
			result += length((std::max)(l, it->first), (std::min)(r, it->second));
		return result;
	}
	std::optional<T> next(T x) const {
		auto it = lower_bound(x);
		if (it == end()) return std::nullopt;
		return (std::max)(x, it->first);
	}
	std::optional<T> prev(T x) const {
		auto it = ranges.upper_bound(x);
		if (it == ranges.begin()) return std::nullopt;
		--it;
		return (std::min)(x, static_cast<T>(it->second - 1));
	}
	T mex(T x = 0) const {
		auto it = find(x);
		return it == end() ? x : it->second;
	}
	std::optional<T> min() const {
		if (empty()) return std::nullopt;
		return begin()->first;
	}
	std::optional<T> max() const {
		if (empty()) return std::nullopt;
		return static_cast<T>(ranges.rbegin()->second - 1);
	}
	size_type size() const { return total; }
	std::size_t interval_count() const { return ranges.size(); }
	bool empty() const { return ranges.empty(); }
	const_iterator begin() const { return ranges.begin(); }
	const_iterator end() const { return ranges.end(); }
	const_reverse_iterator rbegin() const { return ranges.rbegin(); }
	const_reverse_iterator rend() const { return ranges.rend(); }
	void clear() { ranges.clear(); total = 0; }
	void swap(IntervalSet &other) noexcept(std::is_nothrow_swappable_v<Size>) {
		ranges.swap(other.ranges);
		using std::swap;
		swap(total, other.total);
	}
	friend void swap(IntervalSet &a, IntervalSet &b) noexcept(noexcept(a.swap(b))) { a.swap(b); }
};

#endif

Back to top page