快速算法将整数映射到单调递增的整数子集

Question

我遇到了这个问题的多个变种，最近在我的算术编码器实现中成为瓶颈。给定 N (<=256) 个已知非负大小 S_i 的段，从原点开始按顺序排列，并对于给定的 x，我想找到 n，使得

S_0 + S_1 + ... + S_(n-1) <= x < S_0 + S_1 + ... + S_n

问题在于查找和更新的频率大致相同，几乎每次更新都是通过增加一段的大小来完成的。此外，段越大，它被查找或更新的概率就越高。

显然某种类型的树似乎是明显的方法，但我无法想出任何满意利用已知特定领域细节的树实现。

鉴于 N 的相对较小，我也尝试了线性方法，但它们的速度比朴素的二叉树慢得多（即使进行了一些优化，例如从列表的后面开始处理总数超过一半的数字）。

类似地，我测试了引入一个中间步骤，以重新映射值的方式，以保持按大小排序的段，以便对最常用的访问更快，但添加的开销超过了收益。

很抱歉标题不太清楚——尽管这是一个相当基本的问题，但我不知道它有任何特定的名称。

- tohoho

---

非常有趣，我想知道Matlab是如何实现它的。 - Noam M

你能详细说明一下“几乎”这个词在“几乎每次更新都是通过将段的大小增加1来实现”的含义吗？还有其他可能性吗？比如添加/删除段落？增加超过1？减少？ - rici

另外，你尝试过二叉树吗？每个节点包含其左子树的总大小以及自身段的大小。这可以硬编码为256个段，最多需要八次访问来更新或查找任何段。 - rici

分段“按顺序从原点开始布置”是什么意思？它们按长度排序吗？它们按某个空间中的位置排序吗？这是什么空间——它们沿着一条线放置吗？那么它们是如何排序的：按它们的中点位置？按它们的左端点还是右端点？它们可以重叠吗？当它们在“原点”的两侧时，它们是如何排序的——负面的先放置，然后是正面的，还是它们只是按距离交错排列而不考虑方向？... - CiaPan

@rici 我的意思是几乎所有段的总和将在下一次增加时溢出 uint32 的情况。在这种情况下，所有段大小都变为 max(1, previousSize / 2)。这是一个非常罕见的情况，因此性能不是问题（在合理范围内）。至于您的二叉树建议，那基本上就是我的当前实现。虽然性能不是很差，但它仍然是瓶颈，并且还不够快，所以我希望有更好的想法。 - tohoho

Answer 1

我认为一些二叉搜索树可以胜任... 您可以尝试为每个节点添加一个新的数字成员 (int 或 long)，以保留所有左侧后代的值之和。然后，您将在大约对数时间内寻找每个项目，并且一旦添加、删除或修改项目，您将不得不更新递归返回路径上的其祖先。您可以应用一些自组织树结构，例如 AVL 以保持最坏情况下的搜索优化，或者使用伸展树来优化对那些经常使用的项目的搜索。请注意，在重新平衡或伸展期间更新左子树和。

- CiaPan

Answer 2

您可以使用二叉树，其中每个节点n包含两个整数A_n和U_n，最初 A_n = S_0 +..S_n和U_n = 0。

让我们在任何固定的后续时间，T_n = S_0 +..+S_n。

当寻找查询x的位置时，您将沿着树前进，知道对于每个节点m，T_m的当前相应值是A_m + U_m + sum_{p：祖先为m，我们访问了右子节点以达到m} U_p。 这解决了O(log(N))的查找问题。

要更新第n个区间（将其大小增加y），只需在树中查找它，在途中访问的每个节点m上增加U_m og y的值。这也解决了O(log(N))的更新问题。

- vib