sparse table.cpp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using namespace std;
 
#define int long long
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n';
#define yes cout << "YES\n";
#define no cout << "NO\n";
 
 
 
 
 
const int N = 1e6;
 
int table[N][18];

 
void buildSparseTable(int arr[], int n){
    for (int i = 0; i < n; i++) table[i][0] = arr[i]; //change this
    
    for (int j = 1; j <= log2(n); j++)
        for (int i = 0; i <= n - (1 << j); i++)
            table[i][j] = __gcd(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]); //change this
}

 
int query(int L, int R) {
    int j = (int)log2(R - L + 1);
    return __gcd(table[L][j], table[R - (1 << j) + 1][j]); // change this
}
 
int32_t main()
{
    int a[] = { 7, 2, 3, 0, 5, 10, 3, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    buildSparseTable(a, n);
    cout << query(0, 2) << endl;
    cout << query(1, 3) << endl;
    cout << query(4, 5) << endl;
    return 0;
}