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