title: RMQ Problem - ST Table Algorithm

link: RMQ Problem - ST Table Algorithm

catalog: true

lang: en

date: 2020-03-21 20:41:41

subtitle: Preprocessing with O(nlogn) complexity, allows for queries with O(1) complexity.

tags:

- c++
- data structures
- ST table

categories: - [notes, algorithms]

## What is an ST Table?#

An ST table is an algorithm used to solve interval minimum/maximum value queries.

It preprocesses the data with O(nlogn) complexity and allows for queries with O(1) complexity.

**Drawback: Does not support online modifications.**

Template problem: ST Table - Luogu

### 1. Preprocessing#

Use a two-dimensional array dp[i][j] to represent the minimum/maximum value of the range from index i to i + 2^j^ - 1.

The following conditions apply:

① It is easy to see that the boundary condition dp[i][0] is equal to a[i], which means the maximum/minimum value of i~i is the element itself.

② Next is the state transition equation, as shown in the diagram.

1 << j is equivalent to 2^j^#

Initialization code:

```
void init(int n) {
for (int i = 0; i < n; i++) {
dp[i][0] = a[i];
}
for (int j = 1; (1<<j) <= n; j++) {
for (int i = 0; i + (1<<j) <= n; i++) {
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
}
```

### 2. Querying#

Next is the querying process. Since the length of the query interval may not be exactly 2^j, we need the following theorem: (refer to proof by experts)

2^log(a)^>a/2### log(a) represents the largest power of 2 less than or equal to a#

## eg(4)=2,log(5)=2,log(6)=2,log(7)=2,log(8)=3,log(9)=3...#

If we want to find the minimum/maximum value of the interval from a to b, we first calculate the length of the interval as **len = b-a+1** and let **t = log(len)**.

According to the theorem mentioned above, **2^t^>len/2**

This means that 2^t is on the right half of the interval [a, b].

The minimum/maximum value of a and b is equal to min(a ~ (a+2^t^-1), (b-2^t^+1) ~ t), as shown in the diagram.

Querying code:

```
ll sol(int a, int b) {
int t = (int) (log(b-a+1.0)/log(2.0));
return max(dp[a][t], dp[b-(1<<t)+1][t]);
}
```

### 3. Complete Code#

Problem: ST Table - Luogu

AC requires optimization with O2 and fast input reading.

```
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100000;
typedef long long ll;
ll a[maxn];
ll dp[maxn][25]; // Using maximum value as an example here
void init(int n) {
for (int i = 0; i < n; i++) {
dp[i][0] = a[i];
}
for (int j = 1; (1<<j) <= n; j++) {
for (int i = 0; i + (1<<j) <= n; i++) {
dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
}
}
ll sol(int a, int b) {
int t = (int) (log(b-a+1.0)/log(2.0));
return max(dp[a][t], dp[b-(1<<t)+1][t]);
}
int main() {
ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
init(n);
while(m--) {
int x,y;
cin >> x >> y;
cout << sol(x-1,y-1) << endl;
}
return 0;
}
```