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