Sparse Tables

Revision en1, by SHR44, 2022-07-18 23:47:24

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++)
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(log2(r-l+1))][l],st[ll(log2(r-l+1))][r+1-(1<<ll(log2(r-l+1)))]);
}
ll sparse_table::range_min_query(ll l,ll r){
    return std::min(st[ll(log2(r-l+1))][l],st[ll(log2(r-l+1))][r+1-(1<<ll(log2(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.

Tags sparse table, range query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SHR44 2022-07-19 09:56:00 122
en1 English SHR44 2022-07-18 23:47:24 2136 Initial revision (published)