我多次遇到过这个问题的变种,最近它成了我算术编码器实现的瓶颈.给定从原点开始按顺序布置的已知非负尺寸Si的N(<= 256)段,并且对于给定的x,我想找到n使得 S0 S1 … Sn-1< = x< S0 S1 ...... Sn 问题在于查找和更新以大约相同的频率完成,并且几乎每次更新都以将段的大小增加1的形式进行.此外,段越大,查找的概率越大或者再次更新. 显然,某种树似乎是一种显而易见的方法,但我无法提出任何令人满意地利用已知域特定细节的树实现. 考虑到N的相对较小的尺寸,我也尝试了线性方法,但结果却比天然的二叉树慢得多(即使经过一些优化,例如从列表的后面开始,数字超过总数的一半) 类似地,我测试引入了一个中间步骤,重新映射值以保持按大小排序的段,以便为最常用的访问更快,但增加的开销超过了增益. 对不明确的标题感到抱歉 – 尽管它是一个相当基本的问题,我不知道它的具体名称.