我多次遇到过这个问题的变种,最近它成了我算术编码器实现的瓶颈.给定从原点开始按顺序排列的已知非负大小S i的 N(<= 256)段,并且对于给定的x,我想找到n这样的
S0 + S1 + ... + Sn-1 <= x < S0 + S1 + ... + Sn
问题在于查找和更新以大约相同的频率完成,并且几乎每次更新都以将段的大小增加1的形式进行.此外,段越大,查找的概率越大或者再次更新.
显然,某种树似乎是一种显而易见的方法,但我无法提出任何令人满意地利用已知域特定细节的树实现.
考虑到N的相对较小的尺寸,我也尝试了线性方法,但结果却比天然的二叉树慢得多(即使经过一些优化,例如从列表的后面开始,数字超过总数的一半)
类似地,我测试引入了一个中间步骤,重新映射值以保持按大小排序的段,以便为最常用的访问更快,但增加的开销超过了增益.
对不明确的标题感到抱歉 - 尽管它是一个相当基本的问题,我不知道它的具体名称.
我想一些 BST 会做...您可以尝试向每个节点添加一个新的数字成员（int或long）以保留所有左后代的值的总和。然后，您将在大约对数时间内查找每个项目，并且一旦添加、删除或修改了项目，您就必须在递归的返回路径上仅更新其祖先。您可以应用一些自组织树结构，例如 AVL 来保持最坏情况搜索最优，或使用展开树来优化对最常用项目的搜索。请注意在重新平衡或展开期间更新左子树总和。