区间众数指子区间中出现频率最高的元素，难点在于其不可合并性；优化方法依场景而异：离线小值域用Mo’s算法，强制在线小值域用分块预处理，大值域允许误差则用Sketch概率算法。
什么是“区间众数”以及为什么它难优化
区间众数（Mode over range）指对数组某子区间 [l, r]，找出出现频率最高的元素（若有多个，通常返回任意一个）。它和区间最大值、区间和不同——无法用线段树或 ST 表直接合并信息，因为两个区间的众数未必是整体众数。暴力扫描每次 O(n) 查询，q 次就是 O(q·n)，显然不可接受。
关键难点在于：众数不具备可合并性；但高频元素一定来自「候选集」——要么是左/右子区间的众数，要么是跨越中点的某个高频值。不过这个思路仍难高效落地。
Mo’s Algorithm 适合离线+小数据范围
当查询全部已知（离线）、且数组值域较小（如 a[i] ≤ 1e5），Mo’s Algorithm 是最实用的选择。它通过排序查询+双指针移动，均摊每次修改 O(1)，总复杂度约 O((n + q)·√n)。
- 维护一个频次数组
cnt[x]和当前最高频次max_freq - 同时维护一个桶数组
bucket[f]记录频次为f的不同数值个数，但实际只需在增减时更新max_freq - 插入
x：先cnt[x]++，若cnt[x] > max_freq则更新max_freq = cnt[x] - 删除
x：先cnt[x]--，若cnt[x] == max_freq - 1且bucket[max_freq] == 0，则需从头扫cnt找新max_freq（但实践中可懒更新：只在查询时确认，或用set<pair<int, int>>维护(freq, val)）
注意：如果只要求「任一众数」，不必实时维护确切众数，查时遍历所有可能值太慢；推荐配合 vector<int> candidates</int> 缓存当前高频候选（比如只保留 freq ≥ max_freq - 1 的值），查询时在其中试。
立即学习“C++免费学习笔记（深入）”；
值域小+强制在线？用分块预处理众数候选
若必须在线、且 a[i] ∈ [1, K]（K ≤ 2e4），可考虑静态分块：
- 将数组分为
B ≈ √n块，预处理每对块[L, R]的众数（用二维数组mode[L][R]），空间O(n√n) - 查询
[l, r]时，中间完整块的众数已知；两端散块最多2B个元素，枚举它们 + 中间块众数作为候选 - 对每个候选
x，快速统计其在[l, r]内出现次数：预处理每个值x的位置列表，再二分查找（upper_bound - lower_bound）
这样单次查询 O(B log n) ≈ O(√n log n)，比暴力快，且不依赖离线。
常见坑：
- 分块大小选太大（如
B = n/10）导致预处理爆炸 - 忘记散块里可能有新众数（比如中间块众数是 5，但左散块全是 7，右散块全是 7）
- 二分查频次时没用
std::lower_bound而手写错边界
值域大+强制在线+高并发？放弃精确众数，改用 Sketch
若 n, q 达到 1e6 级、值域是 int 范围、且允许一定误差（如返回一个频率 ≥ 实际众数 75% 的元素），就得用概率算法：
- 使用
Count-Min Sketch：固定宽度w、深度d的二维数组，d个哈希函数映射每个值到[0, w) - 插入
x：对每个i ∈ [0, d)，执行sketch[i][h_i(x) % w]++ - 查询
x频次估计：取min_i sketch[i][h_i(x) % w] - 区间查询时，需支持「差分 sketch」——即预处理前缀 sketch 数组，然后用两个前缀 sketch 相减（按位取 min 不可行，得用更稳健的
Count-Sketch或Lossy Counting变种）
但这不是银弹：Sketch 本身不直接给出众数，需配合 Top-k 提取（如维护一个 priority_queue 按估计频次排序，只保留前若干名），且误差随数据分布恶化。
真正上线前务必实测：在你的真实数据上，Count-Min 返回的「众数」是否满足业务容忍的准确率下限。很多场景下，用户其实只需要「高频代表值」，而非严格数学众数。
值域大、在线、精确、快——这四个条件同时满足，在通用 C++ 中没有常数级或对数级解法。能做的，是根据你的 n、q、值域、误差容忍、是否离线，砍掉其中一两条要求。
