For some time, I have been using a specific kind of data structure (I created it while solving a problem without any prior knowledge of the Disjoint Sparse Table). I am pretty sure it is basically a Disjoint Sparse Table, but implemented in a simpler way, so I thought of sharing it.
Prerequisites
The main idea comes from the sliding window technique. Suppose you have q queries where every query has a fixed length (r - l) = k. You can answer each query by combining information from two blocks of size k-1 use the suffix left block and the prefix right block. Then, you can compute the ans using those two values.
Here n = 12, k = 4, and one of the queries is: l = 6, r = 9
So, we create prefix and suffix blocks of size 3. Then, we can computed information from these two blocks to answer the query in O(1).
One example problem:
CSES Sliding Window OrOne very important thing to notice here k-1 makes sure that all l, r are in adjacent blocks. So the block size is not the important part, the main point is that l and r have to belong to some adjacent blocks.
DSL like idea:
Build structure:
Create suffix and prefix blocks with sizes that are powers of 2, So, have to repeat log(n) times. The memory complexity is also O(2 * n log n), and the time complexity is the same.
For n = 12
Build codell pre[N][21];
ll suf[N][21];
// code for rang sum
for(ll i=0,base=1;i<=20;i++,base*=2)
{
pre[0][i]=0;
for(ll j=1;j<=n;j++)
if((j-1)%base==0)pre[j][i]=arr[j];
else pre[j][i]=arr[j]+pre[j-1][i];
suf[n+1][i]=0;
for(ll j=n;j>=1;j--)
if(j%base==0)suf[j][i]=arr[j];
else suf[j][i]=arr[j]+suf[j+1][i];
}
Query structure:
For any query l, r, let x = r - l. l and r will always belong to adjacent blocks, where the block size is either the closest power of 2 to <=x or the next larger power of 2.
Example problem and code:
Static Range Sum Queries
Code#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define memo(a,b) memset(a,b,sizeof(a))
const ll N=2e5+5;
ll pre[N][18];
ll suf[N][18];
int main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);
ll n; cin>>n;
ll m; cin>>m;
ll arr[n+1];
for(ll i=1;i<=n;i++)cin>>arr[i];
for(ll i=0,base=1;i<=17;i++,base*=2)
{
pre[0][i]=0;
for(ll j=1;j<=n;j++)
if((j-1)%base==0)pre[j][i]=arr[j];
else pre[j][i]=arr[j]+pre[j-1][i];
suf[n+1][i]=0;
for(ll j=n;j>=1;j--)
if(j%base==0)suf[j][i]=arr[j];
else suf[j][i]=arr[j]+suf[j+1][i];
}
for(ll i=0;i<m;i++)
{
ll l,r; cin>>l>>r;
if(r-l==0)cout<<arr[l]<<endl;
else
{
ll v=(63 - __builtin_clzll(r-l));
ll val=(1LL<<v);
ll a=(l+val-1)/val;
ll b=(r+val-1)/val;
if(a+1!=b)v++;
cout<<pre[r][v]+suf[l][v]<<endl;
}
}
}
Count maxima on an interval
code#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define memo(a,b) memset(a,b,sizeof(a))
const ll MOD=1e9+7;
const ll N=1e6+5;
pair<int,int>pre[N][22];
pair<int,int>suf[N][22];
int main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);
ll n; cin>>n;
ll arr[n+1];
for(ll i=1;i<=n;i++)cin>>arr[i];
ll mx=(63 - __builtin_clzll(n));
for(ll i=0,base=1;i<=mx;i++,base*=2)
{
pre[0][i]={0,0};
for(ll j=1;j<=n;j++)
if((j-1)%base==0)pre[j][i]={arr[j],1};
else
{
if(arr[j]>pre[j-1][i].first)pre[j][i]={arr[j],1};
else if(arr[j]<pre[j-1][i].first)pre[j][i]=pre[j-1][i];
else {pre[j][i]=pre[j-1][i]; pre[j][i].second++;}
}
suf[n+1][i]={0,0};
for(ll j=n;j>=1;j--)
if(j%base==0)suf[j][i]={arr[j],1};
else
{
if(arr[j]>suf[j+1][i].first)suf[j][i]={arr[j],1};
else if(arr[j]<suf[j+1][i].first)suf[j][i]=suf[j+1][i];
else {suf[j][i]=suf[j+1][i]; suf[j][i].second++;}
}
}
ll m; cin>>m;
ll x,y; cin>>x>>y;
ll z,t; cin>>z>>t;
ll ans=1;
ll lst=0;
for(ll i=0;i<m;i++)
{
ll l=(lst*x+y)%n+1;
ll r=(lst*z+t)%n+1;
if(l>r)swap(l,r);
if(r-l==0){lst=1;}
else
{
ll v=(63 - __builtin_clzll(r-l));
ll val=(1LL<<v);
ll a=(l+val-1)/val;
ll b=(r+val-1)/val;
if(a+1!=b)v++;
auto [v1,c1]=pre[r][v];
auto [v2,c2]=suf[l][v];
if(v1==v2) { ans*=(c1+c2); ans%=MOD; lst=(c1+c2); }
else if(v1>v2) { ans*=c1; ans%=MOD; lst=c1; }
else { ans*=c2; ans%=MOD; lst=c2; }
}
}
cout<<ans<<endl;
}
You might need to join the Codeforces group to access this problem
Comments (0)
