用於處理的時間間隔和點查詢數據結構

Question

我需要知道一個數據結構，其允許我

1）添加的間隔和成本它

2）提取的各點中的最小成本全局區間[1，N]

在這種情況下，可能沒有區間覆蓋點返回INT_MAX。

我試圖使用惰性傳播修改段樹。我應該在每一點做出決定，是否應該更新？它不工作？

我可以在這裏使用稀疏表嗎？

Answer 1

它基本上聽起來像你需要一個interval tree成本間隔映射。

1. 要添加一個區間，只需在樹中添加另一個條目即可。

2. 要執行您編寫的查詢，您要求樹返回與給定點相交的所有條目;給出這個列表，如果它是空的，返回無窮大，否則返回最小值。

第一個查詢的複雜度是間隔數的對數。第二個查詢的複雜度是對數的間隔數+相交間隔數的線性。

（順便說一句，我在Banyan package實現這種東西的Python）。