17370845950

本文介绍在大规模数组上快速响应多组子数组中位数查询的解决方案，针对约束 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() 方法存在三处关键错误：

1. 索引逻辑混乱：arr.length / 2 是向下取整（如长度 6 得 3，但 0-indexed 第 3 位是第 4 个元素）；
2. 错误套用偶数中位数公式：题目只要求单个中位数（⌈len/2⌉），而非偶数长度时的“中间两数平均值”；
3. 未按查询区间切片：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]);
        }
    }
}

⚠️ 关键注意事项：

• 输入 L,R 是 1-indexed，务必转换为 l = L−1, r = R−1；
• 中位数位置 k = ⌈len/2⌉ = (len + 1) / 2（整数除法），对应 0-indexed 下标为 k−1；
• 不要使用 Math.ceil(len/2.0)，避免浮点运算开销；
• 若追求严格 O(Q × len) 最坏性能，可改用 QuickSelect（期望 O(len)），但常数较大，实际未必更快。

? 进阶优化方向（供深入学习）：

• 离线整体二分 + 树状数组：将所有查询和数组值离散化，按答案二分，统计区间内 ≤ mid 的元素个数；
• 主席树（可持久化线段树）：支持 O(log N) 单次查询第 k 小，预处理 O(N log N)，总复杂度 O((N + Q) log N)；
• 莫队算法 + 平衡树：适用于离线且 Q 较大、N 中等的场景。

总结：对于本题约束，正确理解定义 + 规范切片 + Arrays.sort() + 精准索引 是最稳妥、易调试的解法。务必以题干“1-indexed 中位数 = 第 ⌈len/2⌉ 个元素”为准绳，杜绝平均值或索引偏移错误。