algorithm - 区間のセット S が与えられます。与えられた区間 (a, b) に含まれる S のすべての区間を最小時間複雑度で見つける必要があります。

Question

間隔のセットが与えられますS。最小限の時間の複雑さSで、特定の間隔に含まれるすべての間隔を見つける必要があります。(a, b)

O(n)これは力ずくで時間内に実行できます。ここnで、 は set の間隔の数ですS。しかし、前処理を行うことが許可されている場合、これは時間よりも短いO(n)時間で行うことができO(log n)ますか?

最初はinterval treeを考えていましたが、 interval tree は特定の間隔と重なるすべての間隔を取得するために使用されるため、ここでは適用できないと思います。

Answer 1

ここでは、持続的二分探索木を使用できます。

前処理:

1. 空の永続ツリーを作成します。終了点でソートされた間隔を保存する必要があります。
2. 間隔を開始点で並べ替えます。
3. 並べ替えられたリストの最後から開始して、間隔ごとに、永続ツリーの「コピー」を作成し、この間隔をこのコピーに追加します。

探す：

1. 並べ替えられたリストでクエリ間隔の開始点を見つけます。
2. 永続ツリーの対応する「コピー」を、最小のキーからクエリ間隔の最後まで繰り返します。

検索時間の複雑さは O(log(n) + m) です。ここで、m は出力の要素数です。