https://karngyan.com/sparse-tables

MinSparseTable.cpp

//g++  7.4.0

/*
 * Min Sparse Table Example
 *
 * @author Karn, mail@karngyan.com
*/


#include <bits/stdc++.h>

using namespace std;

class MinSparseTable {
    
    int n, P;
    vector<int> log2;
    vector<vector<int>> dp, it;
    int inf = 1e9;
    
public:
    vector<int> values;
    
    MinSparseTable(vector<int> &values) {
        n = values.size();
        P = (int) (log(n) / log(2));
        dp.resize(P+1, vector<int>(n));
        it.resize(P+1, vector<int>(n));
        
        for (int i = 0 ; i < n ; ++i) {
            dp[0][i] = values[i];
            it[0][i] = i;
        }
        
        log2.resize(n+1);
        for (int i = 2 ; i <= n ; ++i)
            log2[i] = log2[i/2] + 1;
        
        for (int p = 1 ; p <= P ; ++p) {
            for (int i = 0; i + (1<<p) <= n ; ++i) {
                int leftInterval = dp[p-1][i];
                int rightInterval = dp[p-1][i + (1 << (p-1))];
                dp[p][i] = min(leftInterval, rightInterval);
                
                if (leftInterval <= rightInterval)
                    it[p][i] = it[p-1][i];
                else
                    it[p][i] = it[p-1][i + (1 << (p-1))];
            }
        }
    }
    
    int MinQuery(int l, int r) {
        int len = r - l + 1;
        int p = log2[len];
        int left = dp[p][l];
        int right = dp[p][r - (1<<p) + 1];
        return min(left, right);
    }
    
    int CascadingMinQuery(int l, int r) {
        int minVal = inf;
        for (int p = log2[r - l + 1] ; l <= r  ; p = log2[r - l + 1]) {
            minVal = min(minVal, dp[p][l]);
            l += (1<<p);
        }
        return minVal;
    }

    int MinIndexQuery(int l,int r) {
        int len = r - l + 1;
        int p = log2[len];
        int left = dp[p][l];
        int right = dp[p][r - (1<<p) + 1];
        if (left <= right)
            return it[p][l];
        return it[p][r - (1<<p) + 1];
    }
};

int main() {
    
    vector<int> values = {1, 2, -3, 2, 4, -1, 5};
    MinSparseTable minSparseTable(values);
    
    cout << minSparseTable.MinQuery(1, 5) << endl; // -3
    cout << minSparseTable.MinIndexQuery(1, 5) << endl; // 2
    
    
    return 0;
}