algorithm - 分块 map 的数据结构

Question

我想制作一个无限平铺 map ，从(-max_int,-max_int)到(max_int,max_int)，所以我要制作一个基本结构: chunk，每个 chunk 包含 char tiles[w][h] 和 int x, y 坐标，所以例如 h=w=10 所以 tile(15,5) 在 chunk(1,0) 中 ( 5,5)坐标，tile(-25,-17)在chunk(-3,-2)上(5, 3)等。现在可以有任意数量的 block ，我需要存储它们并在 O(logn) 或更好的情况下轻松访问它们(如果可能的话 O(1).. 但它是不是.. )。它应该很容易:添加、??删除??(不是必须)和查找。那么我应该使用什么数据结构呢？

Answer 1

读入 KD 树或四叉树(八叉树的二维变体)。这两点在这里可能会有很大帮助。