Sparse Table

Keywords: range minimum query

Sparse Table

這是一個用來找range query min/max的結構，採用的是binary lifting差不多的觀念，也就是倍增法。

• bl[idx][j]：以idx為起點，往右連續2^j筆數值的最大或是最小值
• RMQ[idx1:idx2]：由於記憶體內只有以每個點為出發點，長度為2的冪次方的最大最小值，因此可以將RMQ[idx1:idx2]改成求。

RMQ[idx1:idx1+L - 1] + RMQ[idx2-L+1:idx2]
其中L長度為id1到idx2的全長以下最大的2的冪次方數值

• build 時間複雜度：O(n * log(n))
• query 時間複雜度：O(1)
• 空間複雜度：O(n * log(n))

程式碼

以Leetcde 239. Sliding Window Maximum為例