高效求解区间中位数：离线处理与快速选择优化教程_技术教程

本文讲解如何在多组查询下高效计算任意子数组的中位数，针对 n, q ≤ 5×10⁴ 的约束，指出暴力排序的 o(q·n log n) 不可接受，并给出基于「整体二分」或「主席树」的正解思路，同时修正原始代码中的逻辑错误与边界问题。

在处理大量区间中位数查询（如本题中 Q 可达 5×10⁴）时，对每个查询都复制子数组并调用 Arrays.sort() 是严重低效的——单次排序最坏 O(len log len)，最坏总复杂度可达 O(Q·N log N) ≈ 5×10⁴ × 6×10⁴ × log₂(6×10⁴) > 10⁹ 操作，在 Java 中必然超时。

更关键的是，原始代码存在多重逻辑错误：

❌ median(int N, int[] A) 中 Math.ceil(N / 2) 错误：N/2 是整数除法（如 5/2 = 2），Math.ceil(2) = 2，但题目明确要求 1-indexed 下第 ⌈len/2⌉ 个元素（即下标 ⌈len/2⌉ - 1）。正确写法应为 (N - 1) / 2（奇偶统一）或 (N + 1) / 2 - 1。
❌ 示例输入 {2,4,5,3,1,6} 对应查询 (L,R) 未说明，但输出 3, 4, 5 暗示三组查询（如 [1,3]→[2,4,5]→中位数4？实际应为 4；而 [1,5]→[1,2,3,4,5]→中位数3）。原始代码 getMedian() 并非按 (L,R) 查询，而是不断截取 A[1..mid+1]，与题意完全不符。
❌ getMedian() 递归式缩容无输入依据，属于误解题意。

✅ 正确解法需分场景选择：

场景	推荐方法	时间复杂度	适用性
Q 较小（≤10³）或 N 较小（≤10³）	暴力提取 + 快速选择（nth_element 思想）	O(Q·len) 平均	简单直接，Java 可用 Collections.nthElement 模拟（需转 List）或手写快选
Q, N ≤ 5×10⁴，强制在线	主席树（可持久化线段树）	O((N+Q) log C)	支持任意区间第 k 小，k = (R−L+1+1)/2
Q, N ≤ 5×10⁴，允许离线	整体二分 + 树状数组	O((N+Q) log C log N)	更易实现，常数小

? 推荐实践：使用快速选择优化单次查询（教学友好版）
虽最坏 O(Q·N)，但在随机数据下表现良好，且代码简洁，适合理解核心逻辑：

import java.util.*;

public class MedianQueries {
    // 对子数组 A[L..R]（1-indexed）求中位数：第 k 小，k = (length+1)/2
    public static int queryMedian(int[] A, int L, int R) {
        int len = R - L + 1;
        int k = (len + 1) / 2; // 1-indexed 第 k 小 → 0-indexed 第 k-1 个
        int[] sub = Arrays.copyOfRange(A, L - 1, R); // 转为0-indexed切片
        return quickSelect(sub, 0, sub.length - 1, k - 1);
    }

    private static int quickSelect(int[] arr, int left, int right, int k) {
        if (left == right) return arr[left];
        int pivotIndex = partition(arr, left, right);
        if (k == pivotIndex) {
            return arr[k];
        } else if (k < pivotIndex) {
            return quickSelect(arr, left, pivotIndex - 1, k);
        } else {
            return quickSelect(arr, pivotIndex + 1, right, k);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i++, j);
            }
        }
        swap(arr, i, right);
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }

    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(), R = sc.nextInt();
            System.out.println(queryMedian(A, L, R));
        }
    }
}

⚠️ 注意事项：

题目中“ceil(len/2)”在 1-indexed 下等价于 (len + 1) / 2（整数除法），例如 len=5 → 3，len=6 → 3（不是 3.5 向上取整为 4！因为中位数定义为第 ⌈len/2⌉ 小，6 个数的中位数是第 3 小，非平均）；
Java 中无内置 nth_element，quickSelect 平均 O(n)，最坏 O(n²)，可通过随机化 pivot 优化；
真正工业级解法应采用 主席树：预处理 O(N log C)，单次查询 O(log C)，C 为值域（需离散化），总复杂度 O(N log C + Q log C)，稳定通过 5×10⁴ 数据。