ST table (Spars table) of doubling ideas and data structures
**ST table is a data structure based on the idea of doubling and used to solve the problem of repeatable contribution. **
First, understand what the idea of doubling is. The doubling algorithm, as the name suggests, is to multiply by a power of 2. There are many applications of the doubling algorithm. Here we will focus on explaining the basic usage of doubling and the ST algorithm of RMQ solution.
There is a road now. You have to get from point a to point b, but the total distance is unknown, so there are different ways to go.
- Start from point a and go to point b step by step, as shown in the code below
#include<bits/stdc + + .h>
using namespace std;
#define int long long
signed main()
{<!-- -->
int a,b;
cin>>a>>b;//data guarantee that b is greater than a
while(b!=a)
{<!-- -->
b + + ;
}
return 0;
}`
As you can see, this is a very time-consuming method. At this time, some smart students should say, I can jump two steps at a time, or even jump n steps at a time. It is indeed possible, but if b is much larger than a, there will still be a high complexity (do not directly use b-a The reason is that you don’t know in advance how far the journey is, that is, you don’t know when you will arrive at your destination. Although it can be used, please respect the meaning of the question).
- Use multiplication thinking
#include<bits/stdc + + .h>
using namespace std;
#define int long long
signed main()
{<!-- -->
int a,b;
cin>>a>>b;//data guarantee that b is greater than a
int step=0; //Record the number of steps taken
int i = 0;
while(true)
{<!-- -->
if((a + (1<<i))>b)//If the next step will cross the boundary, reduce the number of steps by half
i--;
else if( (a + (1<<i))<b)//If the next step does not reach the boundary, double the number of steps
{<!-- -->
a + =1<<i;
i + + ;
step + + ;
}
else//At this time, it has just reached the boundary point
{<!-- -->
step + + ;
a + =1<<i;
break;
}
}
cout<<a<<" "<<b<<" "<<step;
return 0;
}
The embodiment of doubling thinking on this question is that I only take one step at the beginning. When I do not reach the boundary, I multiply the number of steps by 2.
For example, our starting point is 1 and the end point is 20. The first time we go to 2, the second time we go to 4, and so on, until I reach the position 16, the next step should be 32 (it takes 16 steps ), but we found that 32>20, we changed the 16 steps into 8 steps, but we found that it was still out of bounds, so we changed it into 4 steps, so that we can reach exactly 20.
After understanding the idea of doubling, it’s time to enter the ST table
As mentioned above, the ST table is based on the idea of doubling. The most widely used field of the ST table is to solve the RMQ problem: given n numbers, asked m times, for each query, the answer interval [l, r] the maximum or minimum value in .
In terms of time complexity, the time complexity of preprocessing of the ST table is O(nlogn), while the time complexity required for each query is only O(1).
Define a two-dimensional array, f[i][j] represents the maximum value from i to i + 2^j-1 with i as the initial point. Obviously f[i][0]=ai, then we can get a formula
f ( i , j ) = m a x ( f ( i , j ? 1 ) , f ( i + 2 ^j ? 1 , j ? 1 ) ).
Let’s talk in detail about how this formula is derived.
For from i to i + 2j, we can divide it into i to i + 2j-1 and i + 2j-1 to i + 2j, so for f[i][j], it is essentially the largest number in these two intervals, and f[i][j-1] and f[i + 2j-1][j-1] itself represents the maximum value between their two intervals, so they only need to be compared (the idea of recursion is used).
The code below shows the preprocessing of the ST table
for (int i = 1; i <= n; i + + ) cin >> stmax[i][0];
for (int j = 1; (1 << j) <= n; j + + )
{<!-- -->
for (int i = 1; i + (1 << j) - 1 <= n; i + + )//Make sure it is a sub-range and does not cross the boundary
{<!-- -->
stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << j - 1)][j - 1]);
}
}
If you want to ask for the minimum value, you only need to change the max function to the min function.
The last step is the query stage, as shown in the code below
int l, r; cin >> l >> r; int x = log_2[r - l + 1]; cout << max(st[l][x], st[r - (1 << x) + 1][x] << endl;
The log_2 function can be rubbed directly by hand, or (int)(log2(r-l + 1)) can be used directly.
Now that you have understood the concept and basic template of the ST table, let’s practice with the board questions
[Template]ST table
Question background
This is a classic ST table question – the maximum value of the static interval
Please note that the maximum data time limit is only 0.8s, and the data intensity is not low. Please make sure that the complexity of each query is
O
(
1
)
O(1)
O(1). If you use a higher time complexity algorithm, there is no guarantee that it will pass.
If you think your code has the right time complexity but TLE, you can try using fast read-in:
inline int read()
{<!-- -->
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){<!-- -->if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' & amp; & amp;ch<='9'){<!-- -->x=x*10 + ch-48;ch=getchar();}
return x*f;
}
The function return value is the first integer read.
Fast reading is only used to speed up reading and is not mandatory.
Title description
Given a length of
N
N
N sequence, and $ M $ queries, find the maximum value of the number in the interval of each query.
Input format
The first line contains two integers
N
,
M
N,M
N and M respectively represent the length of the sequence and the number of queries.
The second line contains
N
N
N integers (denoted as
a
i
a_i
ai?), in turn represents the number of the sequence
i
i
item i.
Next
M
M
M lines, each line contains two integers
l
i
,
r
i
l_i,r_i
li?,ri?, indicating that the query interval is
[
l
i
,
r
i
]
[l_i,r_i]
[li?,ri?].
Output format
The output contains
M
M
M lines, each line contains an integer, representing the result of each query in turn.
Example #1
Sample input #1
8 8 9 3 1 7 5 6 0 8 1 6 1 5 2 7 2 6 1 8 4 8 3 7 1 8
Sample Output #1
9 9 7 7 9 8 7 9
Tips
for
30
%
30\%
30% of the data satisfies
1
≤
N
,
M
≤
10
1\le N,M\le 10
1≤N,M≤10.
for
70
%
70\%
70% of the data satisfies
1
≤
N
,
M
≤
10
5
1\le N,M\le {10}^5
1≤N,M≤105.
for
100
%
100\%
100% data, satisfied
1
≤
N
≤
10
5
1\le N\le {10}^5
1≤N≤105,
1
≤
M
≤
2
×
10
6
1\le M\le 2\times{10}^6
1≤M≤2×106,
a
i
∈
[
0
,
10
9
]
a_i\in[0,{10}^9]
ai?∈[0,109],
1
≤
l
i
≤
r
i
≤
N
1\le l_i\le r_i\le N
1≤li?≤ri?≤N.
Put AC code~
#include<cstdio>
#include<iostream>
using namespace std;
const int N=100001;
int i,j,m,n,l,r,lg[N],st[N][22];
int que(int x,int y)
{<!-- -->
int z=lg[y-x + 1];
return max(st[x][z],st[y-(1<<z) + 1][z]);
}
int main()
{<!-- -->
cin>>n>>m;
lg[0]=-1;
for(i=1;i<=n; + + i)
{<!-- -->
scanf("%d", & amp;st[i][0]);
lg[i]=lg[i>>1] + 1;
}
for(j=1;j<22; + + j)
for(i=1;i + (1<<j)-1<=n; + + i)
st[i][j]=max(st[i][j-1],st[i + (1<<(j-1))][j-1]);
for(i=1;i<=m; + + i)
{<!-- -->
scanf("%d%d", & amp;l, & amp;r);
printf("%d\\
",que(l,r));
}
return 0;
}
Thanks for reading~