题解：区间最值差问题

问题分析

这道题目要求我们处理多个区间查询，每个查询需要求出区间内的最大值与最小值之差。数据规模较大（N≤50000，Q≤200000），普通的暴力解法（每次查询遍历区间）时间复杂度为O(Q*N)，会导致超时，因此需要更高效的算法。

解决方案

我们可以使用线段树来解决这个问题。线段树是一种二叉树形数据结构，适合处理区间查询和更新问题，其构建时间复杂度为O(N)，单次查询时间复杂度为O(logN)，非常适合本题的需求。

线段树实现思路

1. 数据结构设计：每个线段树节点存储区间范围[l, r]、区间最大值fmax和区间最小值fmin
2. 构建线段树：递归构建每个节点，叶子节点对应单个元素，内部节点合并左右子节点的信息
3. 区间查询：递归查找目标区间，合并覆盖区间的最大值和最小值

代码解析

#include <cstdio>
#include <iostream>
#include <algorithm>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;

const int N = 5E4 + 10; // 奶牛数量上限+10
int w[N]; // 存储奶牛身高

// 线段树节点结构
struct node {
    int l, r;       // 区间左右端点
    int fmax, fmin; // 区间最大值和最小值
} t[N << 2];      // 线段树数组，大小通常为4*N

// 合并两个子节点信息到父节点
void pushup(node& p, node& l, node& r) {
    p.fmax = max(l.fmax, r.fmax); // 父节点最大值为左右子节点最大值中的较大者
    p.fmin = min(l.fmin, r.fmin); // 父节点最小值为左右子节点最小值中的较小者
}

// 封装pushup操作，方便调用
void pushup(int x) {
    pushup(t[x], t[x << 1], t[x << 1 | 1]);
}

// 构建线段树
// l, r: 当前处理的区间；x: 当前节点编号（从1开始）
void build(int l, int r, int x = 1) {
    t[x] = {l, r, w[l], w[l]}; // 初始化当前节点的区间和最值
    if (l == r) return; // 叶子节点无需继续构建
    
    int mid = l + r >> 1; // 计算区间中点
    // 递归构建左右子树
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x); // 合并子节点信息到当前节点
}

// 区间查询
// l, r: 目标查询区间；x: 当前节点编号
node ask(int l, int r, int x = 1) {
    if (l <= t[x].l && r >= t[x].r) return t[x]; // 当前节点区间完全包含在查询区间内，直接返回
    
    int mid = t[x].l + t[x].r >> 1; // 计算当前节点区间中点
    
    // 查询区间完全在左子树
    if (r <= mid) return ask(l, r, x << 1);
    // 查询区间完全在右子树
    if (l > mid) return ask(l, r, x << 1 | 1);
    
    // 查询区间跨越左右子树，需要合并左右子树的查询结果
    node L = ask(l, r, x << 1);    // 左子树查询结果
    node R = ask(l, r, x << 1 | 1); // 右子树查询结果
    node res;
    pushup(res, L, R); // 合并左右子树的最值
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m); // 读取奶牛数量和查询数量
    
    rep(i, n) scanf("%d", &w[i]); // 读取每头奶牛的身高
    
    build(1, n); // 构建线段树
    
    while (m--) { // 处理每个查询
        int l, r;
        scanf("%d %d", &l, &r); // 读取查询区间
        
        node res = ask(l, r); // 查询区间最值
        printf("%d\n", res.fmax - res.fmin); // 输出身高差
    }
    
    return 0;
}

算法分析

1. 时间复杂度：

   • 线段树构建：O(N)，每个节点仅处理一次
   • 单次查询：O(logN)，线段树高度为logN，每次查询最多访问logN个节点
   • 总时间复杂度：O(N + QlogN)，适用于题目给定的数据规模

2. 空间复杂度：

   • 线段树数组：O(N)，实际使用4*N的空间存储节点

优化说明

1. 代码中使用了#define rep(i, n)宏定义简化循环，使代码更简洁
2. pushup函数封装了节点合并逻辑，提高代码复用性
3. 递归实现线段树构建和查询，逻辑清晰易读

适用场景

这种线段树解法适用于需要频繁进行区间最值查询的场景，尤其在数据规模较大时优势明显。如果题目中增加区间更新操作，线段树也能高效处理（只需增加pushdown函数实现懒标记）。