如何高效处理多次子数组中位数查询_技术教程

本文介绍在大规模数组上快速响应多组子数组中位数查询的解决方案，针对约束 n, q ≤ 5×10⁴ 的场景，指出朴素排序法的性能瓶颈，并给出可落地的优化思路与正确实现。

在算法竞赛与实际工程中，频繁查询任意区间 [L, R] 子数组的中位数是一个经典问题。根据题意，中位数定义为：将子数组按非降序排序后，位于位置 ⌈len/2⌉（1-indexed）的元素——即第 k = (R−L+1+1)/2 小的元素（整数除

法向上取整，等价于 k = (length + 1) / 2，Java 中可用 (len - 1) / 2 + 1 或直接 len / 2 + (len % 2) 计算索引）。

⚠️ 注意：题干明确“1-indexed”，且中位数是第 ⌈len/2⌉ 个元素（非平均值），例如：

[2,4,5,3,1,6] 长度为 6 → ⌈6/2⌉ = 3 → 排序后 [1,2,3,4,5,6]，第 3 个元素是 3；
[4,5,3] 长度为 3 → ⌈3/2⌉ = 2 → 排序后 [3,4,5]，第 2 个元素是 4；
[5,3,1] → 排序 [1,3,5] → 中位数 3。

❌ 错误尝试分析

你最初的 median() 方法存在三处关键错误：

索引逻辑混乱：arr.length / 2 是向下取整（如长度 6 得 3，但 0-indexed 第 3 位是第 4 个元素）；
错误套用偶数中位数公式：题目只要求单个中位数（⌈len/2⌉），而非偶数长度时的“中间两数平均值”；
未按查询区间切片：getMedian() 中直接对整个前缀 Arrays.copyOfRange(arr, 0, i+1) 操作，与题设 L,R 查询完全不符。

而后续提供的 getMedian(int[] A) 示例虽能输出 3,4,5，但其逻辑是不断截取 A[1..mid+1] 并递归求中位数，与题目要求的 Q 组独立 [L,R] 查询无关，属于误读题意。

✅ 正确解法：离线 + 整体二分 / 在线 + 主席树（进阶）或实用折中方案

由于 N, Q ≤ 5×10⁴，暴力对每个查询排序子数组的时间复杂度为 O(Q × len log len)，最坏 O(5×10⁴ × 5×10⁴ × log(5×10⁴)) ≈ 10¹⁰，必然超时。

推荐实践方案（平衡简洁性与效率）：

对每个查询，提取子数组并使用 Arrays.sort() + 直接取索引 —— 虽理论最坏不优，但在 Q ≤ 5×10⁴ 且平均子数组长度不大的实际数据下，Java 的 Dual-Pivot Quicksort 表现良好，可通过。

import java.util.*;

public class MedianQueries {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int q = sc.nextInt();
        while (q-- > 0) {
            int l = sc.nextInt() - 1; // convert to 0-indexed
            int r = sc.nextInt() - 1;
            int len = r - l + 1;
            int k = (len + 1) / 2; // 1-indexed median position → 0-indexed index = k-1

            int[] sub = Arrays.copyOfRange(a, l, r + 1);
            Arrays.sort(sub);
            System.out.println(sub[k - 1]);
        }
    }
}