c - 快速算法将 int 映射到单调递增的 int 子集

Question

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

S<sub>0</sub> + S<sub>1</sub> + ... + S<sub>n-1</sub> <= x < S<sub>0</sub> + S<sub>1</sub> + ... + S<sub>n</sub>

要注意的是，查找和更新的频率大致相同，几乎每次更新都是将段的大小增加 1。而且，段越大，更新的概率就越高再次查找或更新。

显然，某种树似乎是显而易见的方法，但我无法想出任何能够令人满意地利用已知领域特定细节的树实现。

考虑到 N 的大小相对较小，我也尝试了线性方法，但事实证明它们比简单的二叉树慢得多(即使经过一些优化，比如从列表的后面开始获取超过总数一半的数字)

同样，我测试了引入一个中间步骤，该步骤重新映射值的方式使段按大小排序，从而使最常用的访问速度更快，但增加的开销超过了 yield 。

抱歉标题不明确——尽管这是一个相当基本的问题，但我不知道它的任何具体名称。

Answer 1

我想一些 BST 会做......你可以尝试向每个节点添加一个新的数字成员(int 或 long)以保持值的总和都留下了后代。然后，您将以近似对数的时间查找每个项目，一旦添加、删除或修改了一个项目，您就必须在递归的返回路径上更新其祖先。您可以应用一些自组织树结构，例如 AVL 来保持最坏情况下的搜索最优，或者 splay 树来优化对那些最常用项目的搜索。在重新平衡或展开期间注意更新左子树和。