文章目录
RMQ问题
不带修改的区间最值，重叠的区间不会对区间的最大值产生影响
可以用 ST表（稀疏表）
（不带修改的区间问题可以用，一经修改就不可以用了）
例题模板：区间最值
int dp[8][35];//dp[i][j]表示左端点为i，长度为2^j这样的长度的区间,也就是<==>ans[i][i+2^j-1]
int query(int l, int r )
{
int j = (int)log2(r - l + 1);
return max(dp[l][j], dp[r - (1 << j) + 1][j]);//区间最大值可以有重合覆盖上，右边长度还是j
}
int main()
{
int arr[8] = {
9,3,1,7,5,6,0,8 };
int n = 8;
//填充dp[i][j]
for (int i = 0; i < n; i++)
{
dp[i][0] = arr[i];//ans[i][i+2^0-1]=arr[i]
}
for (int j = 1; j <= log2(n); j++)//j=0已经处理了，先要枚举j，而不是先枚举i，j的最大长度是log2(n);
{
for (int i = 0; i + (1 << j) - 1 < n; i++)// i + (1 << j) - 1是区间的右端点，要小于n,不要越界，
{
dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);//把一个长的区间，把他砍一半，，一半一半的求
//j-1相当于区间长度取了一半，一半一半的求最值
// dp[i][j]的值为，最值（dp[i][j-1]相当于[i][i+2^(j-1)-1]的区间，与[i+2^(j-1)][i+2^(j-1)+2^(j-1)-1]的最值
}
}
int l, r;//左右断电
while (cin >> l >> r)
{
cout << query(l, r) << endl;//query就是询问函数询问l，r的区间最大值
}
return 0;
}
例题：区间最大公约数
int gcd(int a,int b)
{
return b?gcd(b,a%b):0;
}
int dp[8][35];//dp[i][j]表示左端点为i，长度为2^j这样的长度的区间,也就是<==>ans[i][i+2^j-1]
int query(int l, int r)
{
int j = (int)log2(r - l + 1);
return gcd(dp[l][j], dp[r - (1 << j) + 1][j]);//区间最大值可以有重合覆盖上，右边长度还是j
}
int main()
{
int arr[8] = {
9,3,15,12,5,6,0,8 };
int n = 8;
//填充dp[i][j]
for (int i = 0; i < n; i++)
{
dp[i][0] = arr[i];//ans[i][i+2^0-1]=arr[i]
}
for (int j = 1; j <= log2(n); j++)//j=0已经处理了，先要枚举j，而不是先枚举i，j的最大长度是log2(n);
{
for (int i = 0; i + (1 << j) - 1 < n; i++)// i + (1 << j) - 1是区间的右端点，要小于n,不要越界，
{
dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);//把一个长的区间，把他砍一半，，一半一半的求
//j-1相当于区间长度取了一半，一半一半的求最值
// dp[i][j]的值为，最值（dp[i][j-1]相当于[i][i+2^(j-1)-1]的区间，与[i+2^(j-1)][i+2^(j-1)+2^(j-1)-1]的最值
}
}
int l, r;//左右断电
while (cin >> l >> r)
{
cout << query(l, r) << endl;//query就是询问函数询问l，r的区间最大值
}
return 0;
}
区间最大间距
#include<iiostream>
using namespace std;
int dpmax[30][35];
int dpmin[30][35];
//区间最值差
int querymax(int l, int r)
{
int j =(int) log2(r - l + 1);
return max(dpmax[l][j], dpmax[r - (1 >> j) + 1][j] );
}
int querymin(int l, int r)
{
int j = (int)log2(r - l + 1);
return min(dpmin[l][j], dpmin[r - (1 << j) + 1][j]);//区间最大值可以有重合覆盖上，右边长度还是j
}
int main()
{
int n,m;
cin >> n>>m;
int arr[25];
//预处理
for(int i = 0; i < n; i++)
{
cin >> arr[i];
dpmax[i][0] = arr[i];
dpmin[i][0] = arr[i];
}
for (int j = 1; j <= log2(n); j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
{
dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
dpmin[i][j]=min(dpmin[i][j - 1], dpmin[i + (1 << (j - 1))][j-1]);
}
}
while (m--)
{
int l, r;
cin >> l >> r;
cout << querymax(l,r)-querymin(l,r) << endl;
}
return 0;
}