> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/facebook/range-minimum-query-square-root-decomposition-and-sparse-table.md).

# Range Minimum Query (Square Root Decomposition and Sparse Table)

<https://www.geeksforgeeks.org/range-minimum-query-for-static-array/>

**spare table** is 2D k\*i k = floor(log size)

lookuptable 就是I起点 走2^k步，就是1，2，4，8 ....初始化这个表,表里存min的index

query时候就是lookup【l，k】对比lookup\[r-2^k, k] 这俩range有重叠。 哪个range的min小返回哪个

space o(n logn) time o(1)

**square root**

分成√n block 每段里有√n个元素。每次就是中间block和头尾2个edge block算

space time o(√n）

**spare table**

```
import math


class Query:
    def __init__(self):
        self.f = None


    def preprocess(self,arr):
        n = len(arr)
        k = int(math.floor(math.log(n,2)))
        f = [[0]*k for _ in range(n)]
        for i in range(n):
            f[i][0] = i
        i,j=0,1
        while (1<<j) <=n:
            while i+ (1<<j) - 1< n:
                f[i][j] = f[i][j - 1] if arr[f[i][j-1]] < arr[f[i+(1<<(j-1))][j-1]] else f[i+(1<<(j-1))][j-1]
                i+=1
            j+=1
        self.f = f

    def query(self,arr, l,r):
        k = int(math.floor(math.log(r-l+1,2)))
        return arr[self.f[l][k]] if arr[self.f[l][k]] <= arr[self.f[r- (1<<k) +1][k]] else arr[self.f[r- (1<<k) +1][k]]


    def RMQ(self,arr, queries):
        self.preprocess(arr)
        for q in queries:
            print(self.query(arr,q[0],q[1]))
```