本文讲解如何在多组查询下高效计算任意子数组的中位数，针对 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⁴ 数据。
总结：本题本质是「静态区间第 K 小」问题。初学者可从快选入手理解，进阶务必掌握主席树或整体二分——它们是解决大规模区间统计查询的基石工具。
