執筆当初は「区間をペアで管理するやつ」と表記していましたが、「区間をsetで管理するやつ」という表記が一般的に用いられることがあとでわかったため、改題しました（2025/07/14）
区間をsetで管理するデータ構造は、mex（minimum excluded value、含まれない中で最小の値）を高速で求める時などに使われます。C++ での実装はこの記事にまとまっていますが、Python での実装が見当たらなかったため、実装してライブラリにしました。
（2025/04/25 追記）
C++ ですが、より用途が広いライブラリをけんちょんさんが作ってくれました。C+
https://github.com/drken1215/algorithm/blob/master/DataStructure/intervals_management.cpp
（2025/08/25 追記）
「区間をsetで管理するやつ」を統一的に「IntervalSet」と呼んではどうか、という記事を書きました。
時間があれば、一読お願いします。
https://qiita.com/hibit/items/7e27a41212f849179a79
とりあえずコード
from sortedcontainers import SortedSet
class Pairset():
data = None
def __init__(self) -> None:
self.data = SortedSet()
self.data.add((-10**18,-10**18))
self.data.add((10**18,10**18))
def contains(self,x):
idx = self.data.bisect_right((x,10**18))-1
L_start,L_end = self.data[idx]
return x < L_end
def add(self,x):
idx = self.data.bisect_right((x,10**18))-1
L_start,L_end = self.data[idx]
R_start,R_end = self.data[idx+1]
if x < L_end:
return False
if L_end < x and x+1 < R_start:
self.data.add((x,x+1))
elif L_end == x and x+1 < R_start:
self.data.pop(idx)
self.data.add((L_start,x+1))
elif L_end < x and x+1 == R_start:
self.data.pop(idx+1)
self.data.add((x,R_end))
else:
self.data.pop(idx+1)
self.data.pop(idx)
self.data.add((L_start,R_end))
return True
def mex(self,x):
idx = self.data.bisect_right((x,10**18))-1
L_start,L_end = self.data[idx]
if L_end <= x:
return x
else:
return L_end
def expand(self,x):
idx = self.data.bisect_right((x,10**18))-1
L_start,L_end = self.data[idx]
if L_end <= x:
return x,x
else:
return L_start, L_end
def remove(self,x):
idx = self.data.bisect_right((x,10**18))-1
L_start,L_end = self.data[idx]
if L_end <= x:
return False
self.data.pop(idx)
if L_start < x:
self.data.add((L_start,x))
if x+1 < L_end:
self.data.add((x+1,L_end))
return True
sortedcontainers を使用していますが、 tatyam set に慣れている人はそれで済ませるのもありかもしれません
使用法
ps = Pairset()
print(ps.mex(0)) # 0
ps.add(0)
print(ps.mex(0)) # 1
ps.add(2)
print(ps.mex(0)) # 1
ps.add(1)
print(ps.mex(0)) # 3
print(ps.expand(1)) # (0,3)
print(ps.contains(1)) # True
ps.remove(1)
print(ps.contains(1)) # False
print(ps.mex(0)) # 1
解説
以下、計算量について $N$ を使用済の数が連続している区間の数とします。
contains(x)
$x$ が、使用済かどうかを判定します。あれば True、なければ False を返します。
計算量は $O(\text{log}N)$ です。
add(x)
$x$ を使用済にします。すでに使用している場合は何もしませんが、返り値として False を返します。
計算量は $O(\text{log}N)$ です。
mex(x)
$x$ 以上かつ未使用な最小の数を返します。
計算量は $O(\text{log}N)$ です。
expand(x)
$x$ が含まれる連続した使用済の区間（半開区間）を返します。
自分が含まれる区間いっぱいに膨張するイメージです。
$x$ が未使用ならば、(x,x) を返します。
返り値を $L,R$ とすると、$R-L$ がその区間の長さ（連続する使用済みの数の個数）になります。
計算量は $O(\text{log}N)$ です。
remove(x)
$x$ を未使用にします。
元から未使用の場合は何もしませんが、返り値として False を返します。
計算量は $O(\text{log}N)$ です。
使用上の注意
半開区間
参考にした記事は閉区間で管理していましたが、区間長を扱う場合のメリットを考えて、このライブラリでは半開区間を採用しています。
使用法の例では、内部のデータ構造はこうなっています。
つまり、$0,1,2$ が連続していると、その区間は $[0,3)$ になります。
TLE
Python の遅さのせいか、私の実装の悪さのせいなのかはわかりませんが、かなり遅いです。通しはしましたが、数個の TLE が取れずに、定数倍の改善を行った末にやっと間に合ったということがありました。
実際の提出例
今後の展望
- 区間追加
- 区間削除
を追加したいです。
ChatGPT に書かせてできたもの。vereify が済み次第反映させます。
def add_interval(self, xL, xR):
idx = self.data.bisect_left((xL, xR))
if idx > 0:
prev_start, prev_end = self.data[idx - 1]
if xL <= prev_end:
xL = prev_start
xR = max(xR, prev_end)
self.data.pop(idx - 1)
idx -= 1
while idx < len(self.data):
next_start, next_end = self.data[idx]
if next_start > xR:
break
xR = max(xR, next_end)
self.data.pop(idx)
self.data.add((xL, xR))
def remove_interval(self, xL, xR):
idx = self.data.bisect_left((xL, xL))
if idx > 0:
L_start, L_end = self.data[idx - 1]
if L_start <= xL < L_end:
self.data.pop(idx - 1)
if L_start < xL:
self.data.add((L_start, xL))
if xR < L_end:
self.data.add((xR, L_end))
while idx < len(self.data):
L_start, L_end = self.data[idx]
if L_start >= xR:
break
self.data.pop(idx)
if xR < L_end:
self.data.add((xR, L_end))