線段樹查詢爲最大數

Question

我已經給定的n整數的數組A，並且在X D爲每個查詢我必須找到最大元件在子陣列[Ax , A(x-D),A(x-2D)..]

例如形式Q查詢：

A = [1,2,3,4,5,6,17,8] 
we have query 7 2 
Sub Array [17,5,3,1] Ans=17 

我們怎樣才能用的時間複雜度比O(Q*N)因爲沒有索引更新更好的解決這個問題，能不能用一些技術

我不離線解決t認爲Square Decomposition將在這裏工作。

Answer 1

令D大於sqrt(N)。然後序列x，x - d，x - 2 * d，...最多包含sqrt(N)個元素。因此，在這種情況下，每個查詢一個天真的解決方案在O(sqrt(N))工作。

讓D <= sqrt(N)。最多有sqrt(N)這樣不同的D's。讓我們重複它們。對於固定值d，我們可以計算線性時間內所有i的f[i] = max(a[i], f[i - d])（邊界條件需要正確處理）。所有查詢的答案爲(X, D)，其中D = d只是f[X]。

總時間複雜度爲O((N + Q) * sqrt(N))。該解決方案使用線性空間量。