问题描述

给定一个长度为 N 的整数序列，以及 M 次查询。每次查询给出两个整数 X 和 Y，要求输出从第 X 项到第 Y 项之间所有元素的最大值。

输入格式

• 第一行包含两个整数 N 和 M，分别表示序列长度和查询次数。
• 第二行包含 N 个整数，表示原始序列。
• 接下来 M 行，每行包含两个整数 X 和 Y，表示一次区间查询。

输出格式

对于每次查询，输出一行，表示该区间的最大值。

数据范围

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

解决方案：线段树（Segment Tree）

由于查询次数高达 10^6 次，若采用每次遍历区间的方式（时间复杂度 O(M×N)），总时间将不可接受。因此需要使用一种支持高效区间查询的数据结构——线段树。

线段树可以在 O(log N) 时间内完成一次区间最大值查询，建树时间为 O(N)，整体效率远高于暴力方法。

结构定义

每个节点存储当前区间的左右端点及该区间内的最大值。

C++ 实现代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

const int MAXN = 1e5 + 5;

int data[MAXN]; // 原始数组

struct SegmentNode {
    int left, right;
    int maxValue;
};

SegmentNode tree[4 * MAXN];

// 合并子节点信息更新当前节点
void mergeNodes(int index) {
    tree[index].maxValue = max(tree[index * 2].maxValue, tree[index * 2 + 1].maxValue);
}

// 构建线段树
void buildTree(int index, int start, int end) {
    tree[index] = {start, end};
    if (start == end) {
        tree[index].maxValue = data[start];
        return;
    }
    int mid = (start + end) / 2;
    buildTree(index * 2, start, mid);
    buildTree(index * 2 + 1, mid + 1, end);
    mergeNodes(index);
}

// 查询区间 [l, r] 内的最大值
int queryMax(int index, int l, int r) {
    auto &node = tree[index];
    if (l <= node.left && node.right <= r) {
        return node.maxValue;
    }
    int result = INT_MIN;
    int mid = (node.left + node.right) / 2;
    if (l <= mid) {
        result = max(result, queryMax(index * 2, l, r));
    }
    if (r > mid) {
        result = max(result, queryMax(index * 2 + 1, l, r));
    }
    return result;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &data[i]);
    }

    buildTree(1, 1, n);

    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", queryMax(1, x, y));
    }

    return 0;
}