文章目录
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; }
