求区间最大值【线段树&倍增】模板题

先用线段树做了一下，结果用cin超时，数据太变态了，此题正解应该是倍增算法。

先看看线段树怎么做这题；

如果不懂线段树的先看此视频：https://www.bilibili.com/video/BV1cb411t7AM?from=search&seid=13093045061996989240

1.线段树：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 using namespace std;
  5 
  6 constexpr size_t N = 4e5 + 10;
  7 int arr[N], tree[N];
  8 
  9 void build_tree(int node, int start, int end) {
 10 	if (start == end) {
 11 		tree[node] = arr[start];
 12 		return;
 13 	}
 14 	int mid = (start + end) >> 1;
 15 	int left_node =  node << 1;
 16 	int right_node =  (node << 1) + 1;
 17 	build_tree(left_node, start, mid);
 18 	build_tree(right_node, mid + 1, end);
 19 
 20 	tree[node] = max(tree[left_node], tree[right_node]);
 21 }
 22 
 23 int query_tree(int node, int start, int end, int L, int R) {
 24 	if (L > end || R < start)
 25 		return 0;
 26 	else if (L <= start && end <= R)
 27 		return tree[node];
 28 	int mid = (start + end) >> 1;
 29 	int left_node =  node << 1;
 30 	int right_node = (node << 1 ) + 1;
 31 	int left_max = query_tree(left_node, start, mid, L, R);
 32 	int right_max = query_tree(right_node, mid + 1, end, L, R);
 33 	return max(left_max, right_max);
 34 }
 35 
 36 int main() {
 37 
 38 	int n, m;
 39 	scanf("%d%d", &n, &m);
 40 	for (int i = 1; i <= n; ++i) scanf("%d",&arr[i]);
 41 	build_tree(1, 1, n);
 42 	while (m--) {
 43 		int L, R;
 44 		scanf("%d%d", &L, &R);
 45 		printf("%d
",query_tree(1, 1, n, L, R));
 46 	}
 47 }

2.倍增算法（ST）：

倍增看lyd

：https://www.bilibili.com/video/BV14t411t73D?from=search&seid=17507997773809817751

  1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4 
  5 constexpr size_t N = 2e5 + 5;
  6 int dp[N][30];
  7 int a[N];
  8 int n, m;
  9 
 10 void getRMQ() {
 11 	for(int i = 1; i <= n; ++ i) dp[i][0] = a[i];
 12 	for (int j = 1; (1 << j) <= n; ++j) {
 13 		for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
 14 			dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
 15 		}
 16 	}
 17 }
 18 int RMQmax(int l, int r) {
 19 	int k = 0;
 20 	while ((1 << (k + 1)) <= r - l + 1) ++k;
 21 	return max(dp[l][k], dp[r - (1 << k) + 1][k]);
 22 }
 23 
 24 int main() {
 25 	scanf("%d%d", &n, &m);
 26 	for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
 27 	getRMQ();
 28 	int l, r;
 29 	while(m--) {
 30 		scanf("%d%d", &l, &r);
 31 		printf("%d
", RMQmax(l, r));
 32 	}
 33 	return 0;
 34 
 35 }
 36

追求吾之所爱