Sparse Table is a very powerful data structure especially for making range max and min queries.↵
Here is my sparse table class. ↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using ll=long long;↵
#define f(i,x,a) for(ll i=ll(x);i<ll(a);i++)↵
#define LOG(x) 63-__builtin_clzll(x)↵
class sparse_table{↵
public:↵
std::vector<std::vector<ll>>st;↵
std::vector<ll>a;↵
sparse_table(ll n){↵
st.resize(25,std::vector<ll>(n));↵
}↵
void buildst_min();↵
void buildst_max();↵
void buildst_sum();↵
ll range_min_query(ll l,ll r);↵
ll range_max_query(ll l,ll r);↵
ll range_sum_query(ll l,ll r);↵
};↵
void sparse_table::buildst_max(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=std::max(st[i-1][j],st[i-1][j+(1<<(i-1))]);↵
}↵
}↵
}↵
void sparse_table::buildst_min(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<(i-1))]);↵
}↵
}↵
}↵
void sparse_table::buildst_sum(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];↵
}↵
}↵
}↵
ll sparse_table::range_max_query(ll l,ll r){↵
return std::max(st[ll(log2LOG(r-l+1))][l],st[ll(log2LOG(r-l+1))][r+1-(1<<ll(log2LOG(r-l+1)))]);↵
}↵
ll sparse_table::range_min_query(ll l,ll r){↵
return std::min(st[ll(log2LOG(r-l+1))][l],st[ll(log2LOG(r-l+1))][r+1-(1<<ll(log2LOG(r-l+1)))]);↵
}↵
ll sparse_table::range_sum_query(ll l,ll r){↵
std::vector<ll> power_sum;↵
ll k=r-l+1;↵
for(ll i=25;i>=0&&k>0;i--){↵
ll power=ll(pow(2,i));↵
if(power<=k){↵
power_sum.push_back(i);↵
k-=power;↵
}↵
}↵
ll ans=0;↵
ll cur=0;↵
for(auto x:power_sum){↵
// std::cerr<<st[x][l+cur]<<" ";↵
ans+=st[x][l+cur];↵
cur+=ll(pow(2,x));↵
}↵
return ans;↵
}↵
~~~~~↵
You can use this if u find it useful and please do suggest improvements.↵
Here is my sparse table class. ↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using ll=long long;↵
#define f(i,x,a) for(ll i=ll(x);i<ll(a);i++)↵
#define LOG(x) 63-__builtin_clzll(x)↵
class sparse_table{↵
public:↵
std::vector<std::vector<ll>>st;↵
std::vector<ll>a;↵
sparse_table(ll n){↵
st.resize(25,std::vector<ll>(n));↵
}↵
void buildst_min();↵
void buildst_max();↵
void buildst_sum();↵
ll range_min_query(ll l,ll r);↵
ll range_max_query(ll l,ll r);↵
ll range_sum_query(ll l,ll r);↵
};↵
void sparse_table::buildst_max(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=std::max(st[i-1][j],st[i-1][j+(1<<(i-1))]);↵
}↵
}↵
}↵
void sparse_table::buildst_min(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<(i-1))]);↵
}↵
}↵
}↵
void sparse_table::buildst_sum(){↵
ll n=a.size();↵
f(i,0,n){↵
st[0][i]=a[i];↵
}↵
f(i,1,25){↵
for(ll j=0;j+(1<<(i-1))<n;j++){↵
st[i][j]=st[i-1][j]+st[i-1][j+(1<<(i-1))];↵
}↵
}↵
}↵
ll sparse_table::range_max_query(ll l,ll r){↵
return std::max(st[ll(
}↵
ll sparse_table::range_min_query(ll l,ll r){↵
return std::min(st[ll(
}↵
ll sparse_table::range_sum_query(ll l,ll r){↵
std::vector<ll> power_sum;↵
ll k=r-l+1;↵
for(ll i=25;i>=0&&k>0;i--){↵
ll power=ll(pow(2,i));↵
if(power<=k){↵
power_sum.push_back(i);↵
k-=power;↵
}↵
}↵
ll ans=0;↵
ll cur=0;↵
for(auto x:power_sum){↵
cur+=ll(pow(2,x));↵
}↵
return ans;↵
}↵
~~~~~↵
You can use this if u find it useful and please do suggest improvements.↵
