Static Range Minimum Queries

Given an array of n integers, your task is to process q$q$ queries of the form: what is the minimum value in the range [a,b].[a,b]?

Example:

Input:  n = 8, q = 4, a = {3, 2, 4, 5, 1, 1, 5, 3},queries = {{2, 4}, {5, 6}, {1, 8}, {3, 3}}

Output:

2
1
1
4

Approach 1: Using Segment Tree Data Structure

C++

#include <bits/stdc++.h>
using namespace std;
long long arr[1000001];
long long tree[4010001];

void build(long long node,
           long long start, long long end)
{
    if (start == end)
    {
        tree[node] = arr[start];
        return;
    }
    long long mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
long long query(long long node, long long start,
                long long end, long long l, long long r)
{
    if (r < start || l > end)
        return INT_MAX;
    if (l <= start && r >= end)
        return tree[node];
    long long mid = (start + end) / 2;
    long long p1 = query(2 * node, start, mid, l, r);
    long long p2 = query(2 * node + 1, mid + 1, end, l, r);
    return min(p1, p2);
}
int main()
{
    long long n = 8, q = 4;
    vector<long long> a = {3, 2, 4, 5, 1, 1, 5, 3};

    vector<vector<long long>> queries = {{2, 4},
                                         {5, 6},
                                         {1, 8},
                                         {3, 3}};
    for (long long i = 1; i <= n; i++)
        arr[i] = a[i - 1];
    build(1, 1, n);
    for (long long i = 0; i < q; i++)
    {
        long long l = queries[i][0];
        long long r = queries[i][1];

        cout << query(1, 1, n, l, r) << "\n";
    }
    return 0;
}

Approach 2: Using Sparse Table Data Structure

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000001
#define K 25
long long int log1[MAXN + 1];
long long int st[MAXN][K + 1];
long long int arr[1000001];

void log_init()
{
    log1[1] = 0;
    for (long long int i = 2; i <= MAXN; i++)
        log1[i] = log1[i / 2] + 1;
}
void init(long long int n)
{
    for (long long int i = 0; i < n; i++)
        st[i][0] = arr[i];
    for (long long int j = 1; j <= K; j++)
    {
        for (long long int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = min(st[i][j - 1], 
                       st[i + (1 << (j - 1))][j - 1]);
    }
}
long long int query(long long int l, long long int r)
{
    long long int j = log1[r - l + 1];
    long long int min1 = min(st[l][j], st[r - (1 << j) + 1][j]);
    return min1;
}
int main()
{
    long long int n = 8, q = 4;
    vector<long long int> a = {3, 2, 4, 5, 1, 1, 5, 3};

    vector<vector<long long int>> queries = {{2, 4},
                                             {5, 6},
                                             {1, 8},
                                             {3, 3}};
    for (long long int i = 0; i < n; i++)
        arr[i] = a[i];
    init(n);
    log_init();
    for (long long int i = 0; i < q; i++)
    {
        long long int l = queries[i][0];
        long long int r = queries[i][1];

        l--;
        r--;
        cout << query(l, r) << "\n";
    }
    return 0;
}