SQRT分解查詢

Question

我在此網站https://acmcairoscience.wordpress.com/2015/04/06/sqrt-decomposition/

我明白本DS中，我們將輸入陣列分成大小SQRT的桶（N），其中N是的標準算法中讀到的sqrt分解數據結構數組的大小。

但這裏是我不能理解的：輸入查詢的sqrt分解。

假設我們有一些問題給我們一些輸入數據，然後是k個查詢，我們必須處理每個查詢併發出一個響應。我們考慮請求是按照請求的情況（不要改變系統的狀態，但只詢問一些信息）並且修改（即影響系統狀態最初設置爲輸入數據）。

這是我不能理解的給定方法：將大小爲sqrt（k）的桶拆分爲k個查詢，並一次處理每個桶中的所有查詢。

爲什麼我們將查詢分解爲sqrt大小的桶？以及我們如何處理每個桶中的所有查詢？

Answer 1

他沒有將查詢拆分成桶，而是邏輯上將數據拆分成sqrt（k）桶。然後，不是在收到每個查詢時對其進行響應，而是重新排列查詢，以便按範圍順序對它們進行處理。也就是說，在存儲區N中開始的查詢在存儲區N + 1中開始的查詢之前被處理，並且結束於存儲區M中的查詢在存儲區M + 1結束的那些之前被處理。

因此，查詢按從左到右的順序進行處理。

如果有sqrt（n）桶，那麼每個桶的大小是sqrt（n）。假設q = sqrt（n）。

比方說，第一個查詢只是使用桶1.該程序必須爲第一個桶執行q^2計算。然後它會緩存結果，以便從bucket 1開始的任何其他查詢都不必再次進行計算。當程序從左向右處理查詢時，它最終必須爲每個桶執行相同的q^2計算。如果查詢最終使用了所有的桶，那麼我們進行了q次計算，每個計算花費了q^2次。由於q = sqrt（n），所以q * q^2 = sqrt（n）* n。