Python实现特定规则无限重复序列查询的算法优化求助

现有方案的瓶颈 #

你当前把序列的每个元素都存在lst里，当查询位置n很大时，lst的长度会和n等长，内存随n线性膨胀，最终因为存储、读写开销太大超时。但这个序列本身是连续重复同一个数值的分段结构，完全不需要逐位存所有元素。

具体落地方法 #

• 用两个极轻量的状态替代全量lst：
  1. 一个严格递增的starts数组：starts[v]记录数值v在序列中第一次出现的索引位置。
  2. 当前已生成序列的总长度total_len。
• 初始化完全对齐你现在的逻辑：
  初始序列是[0,1,2,2]，对应starts = [0,1,2,4]（依次记录v=0、1、2的起始位置），此时total_len =4。
• 处理每个新自然数v时，不用逐位读lst[v]的值，直接在starts数组上二分查找：找到最大的下标u满足starts[u] <=v，这个u就是序列第v个位置的值——也就是v对应的重复次数cnt[v]。
  因为starts数组是严格递增的，二分查找的运算量极低，时间复杂度只有O(log M)，M是已经记录的分段数量。
• 拿到cnt[v]之后，直接把当前total_len作为新分段的起始位置追加到starts数组，再把total_len更新为total_len + cnt[v]。
• 当total_len超过查询位置n时，直接在starts数组里二分定位n属于哪个分段，返回对应的v值就行，不用继续生成后面的内容。

为什么这个方案比现有实现快很多 #

• 原方案的lst长度和查询位置n线性相关，现在的starts数组长度只和生成过的数值v的数量相关。根据这个序列的增长规律，v的数量是n的2/3次方量级，比如n=2^40的时候，v的数量只有原方案lst长度的万分之一，内存开销大幅降低，数组读写速度也会快很多。
• 你之前查到的“借助列表元素总和优化”的思路，就是这里用到的核心逻辑：序列总长度就是每个分段长度的累加和，不需要逐位存元素，只要记好每个分段的边界，就能靠二分快速定位任意位置的值。

额外的性能细节 #

• 完全不用真的生成重复元素追加到数组里，只要累加总长度就行，省掉了临时列表生成、拷贝的开销。
• 全程用Python原生整数运算，没有浮点数参与计算，完全避开了之前OEIS公式在大n下的精度问题。

内容的提问来源于stack exchange，提问作者Ciprian