带合并单元格的网格：适配O(logN)访问的低内存数据结构选型

问题拆解 #

现有N×M的网格（最小单元格粒度D），原实现通过以下代码定位单元格：

int col = x / dimension; 
int row = y / dimension;
int idx = row * height + col;

该方案内存占用为N×M，且合并单元格时需复制数据，导致严重冗余（比如6×8的1024粒度单元格，会存6×8×16份最小单元格数据）。需要实现一种：

• 访问时间复杂度最高O(logN)
• 内存仅占用实际合并/未合并单元格数量C
• 支持跨象限/兄弟节点合并的方案

核心解决方案：分层区间索引+二分查找 #

设计逻辑 #

因为业务中合并单元格的大小都是D的整数倍（即由k×k个最小单元格组成），我们可以放弃固定网格的存储方式，转而用区间索引+映射表来维护实际存在的单元格：

具体实现 #

1. 单元格存储结构
   每个实际单元格只存必要信息：

• 行覆盖范围：[row_start, row_end)（对应Y坐标范围 [row_start*D, row_end*D)）
• 列覆盖范围：[col_start, col_end)（对应X坐标范围 [col_start*D, col_end*D)）
• 单元格数据实例/指针

2. 快速定位逻辑

• 先计算目标坐标对应的最小单元格基准行/列：

  int base_row = Y / D;
  int base_col = X / D;
  

• 对所有单元格的行区间按row_start排序，用二分查找找到包含base_row的行区间（即满足row_start <= base_row < row_end）
• 同理对列区间排序后二分查找包含base_col的列区间
• 用哈希表维护(row_start, col_start)到单元格的映射，拿到最终目标单元格

3. 合并/拆分操作

• 合并：创建覆盖目标范围的新单元格，删除被合并的小单元格，更新排序后的区间列表和哈希表
• 拆分：删除大单元格，生成对应数量的小单元格，更新索引

复杂度验证 #

• 访问时间：二分查找为O(logC)（C是实际单元格数），满足O(logN)要求
• 内存：仅存储C个单元格，无冗余

替代方案：二维区间树 #

如果需要支持非规则矩形合并（不局限于k×k最小单元格），可以用二维区间树：

• 每个节点存储一个矩形区间，子节点存储该区间内的子区域
• 查找时从根节点向下遍历，匹配包含目标坐标的最上层区间
• 合并时直接新增覆盖目标区域的节点，删除被覆盖的子节点
• 时间复杂度O(logN)，内存占用同样为C

四叉树的适配改造 #

如果想基于已了解的四叉树优化，解决跨象限合并问题：

• 打破严格四等分限制，允许节点存储任意矩形区间（比如跨两个象限的大单元格）
• 查找时优先匹配最上层的覆盖节点，无需严格遍历四叉分支
• 改造后的四叉树本质是灵活的区间树，完全满足需求

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