动态数组区间不同整数统计及更新查询的内存优化解法问询

问题回顾 #

给定长度为N的整数数组a[i]（1 ≤ N, Q ≤ 1e5，1 ≤ a[i] ≤ 1e6），处理两类查询：

1. 查询区间[l,r]内不同整数的数量
2. 将数组第i位的值修改为x

你之前用分块（sqrt分解）的布尔表方案内存超限，下面是几种更省内存且效率达标的解法：

解法1：改进版分块（内存优化） #

原分块方案用每个块对应大小为1e6的布尔数组，总内存易超限。优化思路如下：

• 把每个块的布尔表替换为哈希表/字典，仅存储该块内出现过的元素及其计数，而非全量覆盖1e6范围的数组。这样每个块的内存仅与块内不同元素数量相关，实际占用远低于全量数组。
• 查询流程：
  • 遍历两端不完整的块，用临时哈希表记录出现过的元素
  • 遍历中间完整的块，将块哈希表中的元素合并到临时哈希表（自动去重）
  • 临时哈希表的大小即为答案
• 修改流程：
  • 找到目标元素所在块，将旧值的计数减1，若计数为0则从块哈希表中删除该键
  • 将新值的计数加1，若该值未在哈希表中则新增键值对
  • 更新数组对应位置的值
• 时间复杂度仍为O(sqrt(N))，内存占用大幅降低。

解法2：线段树+哈希表 #

用线段树维护区间元素的出现情况，每个线段树节点存储对应区间的哈希表：

• 每个节点的哈希表记录区间内各元素的出现次数
• 查询时，递归合并查询区间覆盖的线段树节点哈希表，统计计数≥1的元素总数
• 修改时，从叶子节点向上更新路径上所有节点的哈希表：删除旧值（计数减至0则移除），添加新值
• 时间复杂度：查询与修改均为O(logN * K)（K为合并时处理的不同元素数量），对于1e5规模的数据完全可行；内存上，线段树共4*N个节点，每个节点仅存储对应区间的不同元素，总占用远低于全量分块布尔表。

解法3：带修改的Mo算法（时间换空间） #

也叫三维Mo算法，将修改操作作为第三维调整查询排序逻辑：

• 把每个查询拆分为(l, r, t)，其中t为当前已执行的修改次数
• 排序规则：以l所在块为第一关键字，r所在块为第二关键字，t为第三关键字（可加奇偶排序优化减少指针移动次数）
• 维护当前区间[cur_l, cur_r]和当前修改次数cur_t，通过移动指针、回退/应用修改调整到目标查询状态；用大小为1e6的计数数组cnt[]记录元素出现次数，用ans统计当前不同元素数量（cnt[x]从0变1时ans加1，从1变0时ans减1）
• 内存方面：仅需约4MB的计数数组（int类型1e6个元素），加上少量变量与查询存储数组，完全符合512MB限制
• 时间复杂度：O(N*sqrt(N))，通过快读快写、奇偶排序等常数优化后，可处理1e5规模的数据。

解法4：前缀和+树状数组（离线场景） #

若所有查询与修改可提前获取（离线处理），可采用此方法：

• 将原数组元素视为初始修改操作，把所有操作按时间顺序排序
• 用树状数组维护每个元素最后出现的位置，查询[l,r]转化为统计r位置前，最后出现位置≥l的元素数量
• 修改时，先删除旧元素的最后出现位置，再将新元素的当前位置作为其最后出现位置加入树状数组
• 时间复杂度O((N+Q)logN)，内存占用极小，适合离线场景。

内容的提问来源于stack exchange，提问作者Tomek Swiecki