SHR44's blog

Sparse Tables
By SHR44, history, 2 years ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

maybe you can precompute the log2 value since the math log2 is slow?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is also prone to precision errors. a good way to do this is to use: 31-__builtin_clz(x), this gives you the highest power of 2 in x. using this you can avoid precomputation too.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Q.1) Is there any site from which i can copy paste most of these data structures like segment tree, fenwick tree etc..

Q.2) how to implement something like lazy propogation in fenwick tree. any link to learn that please.

→ Reply