RMQ problem - ST table algorithm

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;
}

cos