分段樹中的存儲時間

我想知道爲解決最小查詢範圍問題而生成的分段樹中有多少個節點。分段樹中的存儲時間

另外，構建操作需要多長時間？爲什麼？

來源

2013-01-18 vishalgoel

您指的是哪種RMQ算法？ – templatetypedef

如果u使用線段樹，構建是O（nlgn），每個查詢是O（LGN）

如果數組是靜態的，U也可以嘗試另一種算法RMQ。構建時間是O（nlgn），每個查詢只有O（1）。

來源

2013-01-18 09:22:39 songlj

爲什麼建立時間O（nlogn）？據我所知，總共有2n-1個節點。作爲一個例子N = 16。所以節點1是1-16，節點2是1-8，節點3是9-16。當我們繼續分割時，我們看到有2n-1個節點。並且對於每個節點，只進行一次比較。所以時間是O（2n-1）或O（n）。 plz解釋我是如何的時間是O（nlogn） – vishalgoel

線段樹的複雜性：

初始化逐個元素：O（NLogN）從陣列
初始化：O（N）
查詢範圍：O（logN）的
插入（更新）元素：O（logN）

來源

2013-01-18 13:46:34

分段樹中的存儲時間

回答

相關問題