### SHR44's blog

By SHR44, history, 6 months ago,

When I try to submit a problem in the credit suisse global coding challenge, it says the following

Oops — Something's Gone Wrong Sending the Code to the Server Request Failed with Status Code: 400

What should I do now??

• +4

By SHR44, history, 8 months ago,

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.

• +16