1270 数列区间最大值（线段树）

青旅半醒 2022-09-03 14:17 144阅读 0赞

**1. 问题描述：**

输入一串数字，给你 M 个询问，每次询问就给你两个数字 X，Y，要求你说出 X 到 Y 这段区间内的最大数。

**输入格式**

第一行两个整数 N，M 表示数字的个数和要询问的次数；  
接下来一行为 N 个数；  
接下来 M 行，每行都有两个整数 X，Y。

**输出格式**

输出共 M 行，每行输出一个数。  
数据范围  
1 ≤ N ≤ 10 ^ 5,  
1 ≤ M ≤ 10 ^ 6,  
1≤ X ≤ Y ≤ N,  
数列中的数字均不超过2 ^ 31−1

**输入样例：**

10 2  
3 2 4 5 6 8 1 2 9 7  
1 4  
3 8

**输出样例：**

5  
8

来源：[https://www.acwing.com/problem/content/description/1272/][https_www.acwing.com_problem_content_description_1272]

**2. 思路分析：**

分析题目可以这是一道求区间最值的问题，因为不涉及到区间的修改所以我们可以使用**ST表（不支持区间的修改）**或者是**线段树**解决，下面使用线段树来解决，线段树的一个缺点是很容易超时，当数据量超过10 ^ 6之后大部分情况下会超时，当数据量在10 ^ 5以内操作次数比较少的前提下一般是可以通过的。线段树可以解决大部分与区间相关的动态问题，涉及到区间中某个位置或者某一段区间进行修改的时候一般使用线段树来解决。这道题目类似于求解区间和，我们只需要将求解区间和的代码修改为求解区间最大值的代码即可，其余的代码都是不需要修改的，与acwing的[1264][]题是类似的，可以发现线段树的中区间相关的问题可以通过修改每个节点的动态信息维护区间的动态信息，动态信息包括区间和，区间最大值等等，修改每个节点的过程其实是一个递归的过程。

**3. 代码如下：**

**java代码（超时）：**

import java.util.Scanner;
    public class Main {
        static Tree tr[];
        static int nums[];
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n, m;
            n = sc.nextInt();
            m = sc.nextInt();
            // 注意线段树下标从1开始比较方便, 所以声明n + 1的长度
            nums = new int[n + 1];
            tr = new Tree[4 * n];
            for (int i = 1; i < 4 * n; ++i) {
                tr[i] = new Tree(0, 0, 0);
            }
            for (int i = 1; i <= n; ++i){
                nums[i] = sc.nextInt();
            }
            build(1, 1, n);
            while (m > 0){
                int x, y;
                x = sc.nextInt();
                y = sc.nextInt();
                int res = query(1, x, y);
                System.out.println(res);
                m --;
            }
        }
    
        // 创建线段树
        public static void build(int u, int l, int r){
            if (l == r){
                tr[u].l = tr[u].r = l;
                tr[u].maxv = nums[l];
            }else {
                // 递归创建
                int mid = l + r >> 1;
                tr[u].l = l;
                tr[u].r = r;
                build(u << 1, l, mid);
                build(u << 1 | 1, mid + 1, r);
                // 递归返回到当前这一层的那么计算以当前根节点对应区间的最大值, 往上传递
                tr[u].maxv = Math.max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
            }
        }
    
        // 区间查询操作
        public static int query(int u, int l, int r){
            if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
            int s = -100000000;
            int mid = tr[u].l + tr[u].r >> 1;
            if (mid >= l){
                s = query(u << 1, l, r);
            }
            if (mid < r){
                s = Math.max(s, query(u << 1 | 1, l, r));
            }
            return s;
        }
    
        public static class Tree{
            int l, r, maxv;
            public Tree(int l, int r, int maxv){
                this.l = l;
                this.r = r;
                this.maxv = maxv;
            }
        }
    }

**c++代码：**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <climits>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int w[N];
    struct Node
    {
        int l, r;
        int maxv;
    }tr[N * 4];
    
    void build(int u, int l, int r)
    {
        if (l == r) tr[u] = {l, r, w[r]};
        else
        {
            tr[u] = {l, r};
            int mid = l + r >> 1;
            build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
            tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
        }
    }
    
    int query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
        int mid = tr[u].l + tr[u].r >> 1;
        int maxv = INT_MIN;
        if (l <= mid) maxv = query(u << 1, l, r);
        if (r > mid) maxv = max(maxv, query(u << 1 | 1, l, r));
        return maxv;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    
        build(1, 1, n);
    
        int l, r;
        while (m -- )
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
    
        return 0;
    }

[https_www.acwing.com_problem_content_description_1272]: https://www.acwing.com/problem/content/description/1272/
[1264]: https://blog.csdn.net/qq_39445165/article/details/119491922