Sparse Table (RMQ) - YessineJallouli/Competitive-Programming GitHub Wiki
#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;
const int N = 3e5+7;
const int LOG = 20;
ll Sp[N][LOG];
ll a[N];
int n;
void build() {
for (int i = 0; i < n; i++)
Sp[i][0] = a[i];
for (int j = 1; j < LOG; j++) {
for (int i = 0; i+ (1<<j)-1 < n; i++) {
Sp[i][j] = min(Sp[i][j-1], Sp[i+(1<<(j-1))][j-1]);
}
}
}
ll get(int qs, int qe) {
int len = qe-qs+1;
int k = 0;
while (1 << (k+1) <= len)
k++;
return min(Sp[qs][k], Sp[qe-(1<<k)+1][k]);
}
int main()
{
SaveTime
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
build();
}
Resources :
https://youtu.be/0jWeUdxrGm4
Problems :
https://codeforces.com/contest/1549/problem/D