範圍最小/最大查詢

我有座標點（x，y）說我有10000點。現在當一個新點被給出爲測試查詢說（p，q）時。我要檢查每點座標points.if X文本查詢是座標 PY 從網上搜索我才知道，Rmq-範圍最小/最大的查詢數據結構可以幫助我，但我不知道該怎麼辦呢..can有人幫助我如何可以我這樣做..any引用或C++代碼的幫助將是很大的幫助。謝謝範圍最小/最大查詢

來源

2011-08-25 Nichole Grace

你能澄清你在問什麼嗎？你想對測試點做什麼？你想找到最接近它的地方嗎？你是否試圖檢查數據集中是否存在該點？ – templatetypedef

我試圖找到，如果數據集中 –

點退出更準確地說我試圖讓。那是，如果在與後綴數組檢查..一個字符串，然後它給包圍了所有後綴範圍的輸入文本的後綴數組範圍。現在我設法得到後綴輸入文本的後綴數組的範圍。現在我試圖看看輸入文本的後綴範圍是測試字符串的前綴。要測試這個，我可能不得不使用rmq或一些好的數據結構來檢查這種情況的時間效率 –

如果你的目標是要檢查數據集是否存在該點，則有是一些可用於保存數據的非常有用的數據結構，每個數據結構都支持非常高效的查找。

對於初學者來說，如果你需要知道的就是點是否存在，你總是可以存儲在一個標準的哈希表或平衡二叉搜索樹中的所有點。這將分別提供O（1）或O（log n）查找時間。再加上這些結構在大多數編程語言中都是可用的。另一方面，如果您計劃對數據進行更有趣的操作，例如搜索距離某個測試點最近的數據集中的k個點，或試圖找到某些邊界中的所有點區域，您可能需要考慮使用kd-tree或quadtree。這些標準二進制搜索的變體提供了快速查找（O（log n）時間）。 kd-tree還支持非常快速的k-nearest-neighbor searches並在邊界卷內進行搜索。此外，如果您有任何實現標準二叉搜索樹的經驗，kd-tree會非常容易實現。

希望這會有所幫助！

來源

2011-08-25 00:58:57 templatetypedef

範圍最小/最大查詢

回答

相關問題