1.ST表求解

ST表的實質其實是動態規劃，下面是區間最小的遞歸公式，最大只需將min改成max即可

f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

二維數組的f[i][j]表示從i開始連續2*j個數的最小/大值。

例如：我們給出一個數組a[10]={0,1,2,4,6,7,9,2,12,3};

我們可以給f[i][0]....f[n][0]先初始化為上面數組的值，我們將f[i][j]分為兩端，一段是i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1,f[i][j]就是分出來的這兩個段的最大/小值。

于是有了遞歸公式。

寫一道例題

P1816 忠誠 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 100010;
const int M = 20;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
int n, a[N], f[N][M],m[N][M];
//創建ST表
void create() {//初始狀態//f[i][0]表示從i開始長度為2^0的區間最值為a[i]本身for(int i = 1; i <= n; i ++) f[i][0] = a[i],m[i][0]=a[i];int k = log2(n);//枚舉區間長度指數jfor(int j = 1; j <= k; j ++)for(int i = 1; i + (1 << j) - 1 <= n; i ++){f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);m[i][j] = min(m[i][j - 1], m[i + (1 << j - 1)][j - 1]);}}
//利用ST表查詢區間[L,R]的最大值
int query1(int L, int R) {int k = log2(R - L + 1);return max(f[L][k], f[R - (1 << k) + 1][k]);
}
int query2(int L,int R)
{int k=log2(R-L+1);return min(m[L][k], m[R - (1 << k) + 1][k]);
}
int main()
{int m;cin >> n >> m;for(int i = 1; i <= n; i ++) scanf("%d", a + i);create();while(m --) {int L, R;scanf("%d%d", &L, &R);printf("%d ", query2(L,R));}
}

其實就是區間最小值。

2.線段樹

線段樹其實也就是相當于區間分段，(a,b)的左孩子區間就是(a,(a+b)/2)和右孩子((a+b)/2+1,b)，(a.b)區間的最值就是他分出的兩個區間的最值的最值。

對于上道例題的代碼：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 2000010;
const int M = 1e9+2;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
ll n, m, a[N];
struct Node
{int l, r, minn = mod;
}tree[N];
void build(int i, int l, int r)
{tree[i] = { l,r };if (l == r){tree[i].minn = a[l];return;}int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);tree[i].minn = min(tree[i << 1].minn, tree[i << 1 | 1].minn);
}
int ask(int i, int l, int r)
{if (l == tree[i].l && r == tree[i].r) return tree[i].minn;int mid = tree[i].l + tree[i].r >> 1;if (r <= mid) return ask(i << 1, l, r);if (l > mid) return ask(i << 1 | 1, l, r);return min(ask(i << 1, l, mid), ask(i << 1 | 1, mid + 1, r));
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);for (int i = 1; i <= m; i++){int l, r;cin >> l >> r;cout << ask(1, l, r) << " ";}
}
int main()
{TEST2solve();return 0;
}

3.其他例題

1.奶牛排隊

1274. 奶牛排隊 - AcWing題庫

區間最大值與最小值的差

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 100010;
const int M = 20;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
int n, a[N], f[N][M],m[N][M];
//創建ST表
void create() {//初始狀態//f[i][0]表示從i開始長度為2^0的區間最值為a[i]本身for(int i = 1; i <= n; i ++) f[i][0] = a[i],m[i][0]=a[i];int k = log2(n);//枚舉區間長度指數jfor(int j = 1; j <= k; j ++)for(int i = 1; i + (1 << j) - 1 <= n; i ++){f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);m[i][j] = min(m[i][j - 1], m[i + (1 << j - 1)][j - 1]);}}
//利用ST表查詢區間[L,R]的最大值
int query1(int L, int R) {int k = log2(R - L + 1);return max(f[L][k], f[R - (1 << k) + 1][k]);
}
int query2(int L,int R)
{int k=log2(R-L+1);return min(m[L][k], m[R - (1 << k) + 1][k]);
}
int main()
{int m;cin >> n >> m;for(int i = 1; i <= n; i ++) scanf("%d", a + i);create();while(m --) {int L, R;scanf("%d%d", &L, &R);printf("%d\n", query1(L,R)-query2(L,R));}
}

2.求m區間內的最小值

P1440 求m區間內的最小值 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 2000010;
const int M = 1e9 + 2;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
ll n, m, a[N];
struct Node
{ll l, r, minn = mod;
}tree[N];
void build(int i, int l, int r)
{tree[i] = { l,r };if (l == r){tree[i].minn = a[l];return;}int mid = l + r >> 1;build(i << 1, l, mid);build(i << 1 | 1, mid + 1, r);tree[i].minn = min(tree[i << 1].minn, tree[i << 1 | 1].minn);
}
int ask(int i, int l, int r)
{if (l == tree[i].l && r == tree[i].r) return tree[i].minn;int mid = tree[i].l + tree[i].r >> 1;if (r <= mid) return ask(i << 1, l, r);if (l > mid) return ask(i << 1 | 1, l, r);return min(ask(i << 1, l, mid), ask(i << 1 | 1, mid + 1, r));
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);for (int i = 1; i <= n; i++){if (i == 1){cout << "0\n";continue;}int l=max(1ll,i-m), r=i-1;cout << ask(1, l, r) << "\n";}
}
int main()
{TEST2solve();return 0;
}

用單調隊列更簡單。。。