如何以低于O(QN)的时间复杂度从区间查询生成频率数组

核心思路：差分数组（前缀和技巧） #

常规展开区间统计的时间复杂度是O(QN)，当查询数量Q或区间范围N较大时效率极低，差分数组法可以将时间复杂度降到O(Q+N)，是当前最优的实现方式。

具体步骤 #

假设需要统计的元素范围是[min_val, max_val]（比如示例中的1到4）：

1. 初始化差分数组
   创建一个长度为max_val + 2的数组diff，初始值全为0。多开一个位置是为了处理end+1超出原范围的边界情况。
2. 遍历所有区间更新差分数组
   对每个区间[start, end]，执行两个操作：
   • diff[start] += 1：标记区间起始位置的频率增量
   • diff[end + 1] -= 1：标记区间结束后下一个位置的频率减量
     以示例中的三个区间为例：
   • 处理[1,3]：diff[1] +=1，diff[4] -=1
   • 处理[2,3]：diff[2] +=1，diff[4] -=1
   • 处理[3,4]：diff[3] +=1，diff[5] -=1
     最终diff数组（索引从0开始）为：[0, 1, 1, 1, -2, -1]
3. 计算前缀和得到频率数组
   从min_val开始遍历diff数组，累加当前值得到对应元素的频率：
   • 元素1：累加diff[1] → 1
   • 元素2：累加diff[2] → 1+1=2
   • 元素3：累加diff[3] → 2+1=3
   • 元素4：累加diff[4] → 3+(-2)=1
     最终得到目标频率数组[1, 2, 3, 1]

适配稀疏元素场景 #

如果元素范围极大（比如从1到1e9）或者元素不连续，直接用数组会浪费空间，此时可以用**哈希表（字典）**替代数组：

• 用字典存储需要增减的位置和对应数值，比如对区间[start, end]，在字典中start对应值+1，end+1对应值-1（不存在则设为-1）
• 将字典的键排序后，按顺序遍历计算前缀和，同时记录每个元素的频率

时间复杂度分析 #

• 处理Q个区间：O(Q)
• 计算前缀和得到频率：O(N)（数组场景）或O(K log K)（哈希表场景，K为不同的位置数，通常远小于N）
  整体复杂度远低于O(QN)，在大规模数据下优势显著

内容的提问来源于stack exchange，提问作者Aman Singh Rajpoot