题目分析

本题要求实现一个数据结构，支持一种查询操作：

区间众数查询：查询区间 $[l, r]$ 内出现次数最多的数（众数）

如果多个数出现次数相同，选择数值最小的作为答案

算法设计

区间众数问题是一个经典难题，因为众数不具有区间可加性，不能像求和那样简单合并。我们需要设计特殊的方法来处理。

分块算法与预处理

我们采用分块算法，并进行精心预处理：

离散化：将原始数据映射到较小的值域

预处理每块的频率信息

预处理块间的众数信息

查询时结合预处理信息和边界处理

核心思想

预处理所有块对的众数信息

查询时，众数要么是中间整块的众数，要么出现在边界块中

通过预处理减少查询时的计算量

算法复杂度分析

时间复杂度 预处理阶段：

离散化：$O(n \log n)$

预处理频率数组：$O(n \sqrt{n})$

预处理众数信息：$O(n \sqrt{n})$

查询阶段：

平均情况：$O(\sqrt{n})$

最坏情况：$O(\sqrt{n})$

空间复杂度 $O(n \sqrt{n})$：存储预处理信息

$O(n)$：存储数组和其他辅助信息

关键优化点

离散化处理：

将大数据范围映射到连续小范围

减少空间占用和提高缓存效率

频率预处理：

预处理每个块的累计频率

快速计算任意块区间的频率

众数预处理：

预处理所有块对的众数信息

查询时直接使用预处理结果

边界处理优化：

只检查边界块中的候选元素

利用预处理信息减少计算量

性能分析

预处理开销 预处理阶段虽然时间复杂度较高，但只需执行一次，对于大量查询来说是值得的。

查询效率 查询时只需处理边界块，大大减少了计算量，使得单次查询效率很高。

空间权衡 通过离散化减少了值域空间，虽然预处理需要额外空间，但在可接受范围内。

扩展思考

区间众数问题还有其他解决方法：

摩尔投票法的扩展版本

持久化数据结构（如持久化线段树）

随机化算法（适用于近似查询）

每种方法在不同场景下各有优劣，分块方法在预处理和查询之间取得了很好的平衡。

代码总结

本题展示了如何通过分块算法解决复杂的区间众数查询问题。通过精心设计的预处理策略，我们将查询复杂度降低到可接受的范围。

核心技术：

离散化减少值域

频率信息预处理

众数信息预处理

边界候选检查

这种"预处理+边界处理"的思路可以应用于其他复杂的区间查询问题，特别是在需要处理不可加性信息时。