大规模有序图表数据区间删除后 如何高效求解新的y值最大值

有完全匹配你需求的成熟实现路径，不需要退回到全量遍历，直接解决你之前遇到的「分段索引偏移需要重算全部关联」「SortedSet不支持重复值」的痛点，同时兼容你现有场景下的重复值、负值、NaN等特殊数据情况。

低改造成本的实用方案（实际运行无延迟感知） #

这个方案是对你之前想到的「分段存储自身最大值」思路的直接优化，从根本上解决索引偏移的问题：

• 按固定块大小（建议64/128/256个数据点）把数据集拆成独立的块，每个块单独维护两个核心值：当前块内的有效数据点数量、块内y值的最大值（计算时自动跳过NaN）
• 块之间按数据存储顺序用简单链表串联，完全不需要维护全局连续的固定索引映射：所有「从有效索引i开始删除m个点」的操作，只要顺着链表累计每个块的有效点数，就能快速定位起始位置所属的块、删除范围覆盖到的所有块
  • 参考性能：如果块大小取256，哪怕数据集规模n达到1e7，总块数也不到4万个，定位目标位置的开销极低
• 全局最大值不需要每次重算，只需要维护一个块最大值的计数字典：记录当前有多少个块的最大值等于某个y值。每次删除操作涉及到的块，只需要重新计算当前块的新最大值，删掉该块旧的最大值计数，加上新的最大值计数，全局最大值直接取字典里的最大key即可
• 这套逻辑完全绕开了SortedSet的重复值问题：就算有多个块、块内多个点的y值相同，只要计数不降到0，这个值就会保留在全局最大值的候选里，根本不需要依赖不支持重复值的有序集合
• 这套方案的实际运行效率远好于理论值：因为块的尺寸很小，计算块内最大值的操作完全在CPU缓存范围内，就算n达到千万级，单块重算的耗时也远低于1微秒

严格O(log n)复杂度的极致方案 #

如果你需要严格的对数级复杂度保证，只需要把上面的块结构升级为平衡顺序统计树的节点即可：

• 每个树节点对应一个固定大小的数据块，除了存储块内的实际数据、块内y值最大值，还要额外维护两个树结构所需的统计值：
  • 当前节点为根的子树一共包含多少个有效数据点（支持快速定位第i个有效点的位置，实现顺序统计能力）
  • 当前节点为根的子树整体的y值最大值
• 所有操作的复杂度都是严格O(log n)：
  • 定位起始索引i的位置：顺着树结构靠子树大小遍历，不需要遍历所有元素
  • 处理连续m个点的删除：拆分、删除覆盖到的树节点，同步更新沿途节点的子树大小、子树最大值、块内最大值
  • 获取全局最大值：直接读取树根节点存储的整棵树的子树最大值即可，不需要额外查询
• 重复值、NaN的处理逻辑和前面的分块方案完全一致：最大值计算时跳过NaN，不要求值唯一，根本不会受重复值的影响

和现有实现的对比 #

• 你当前采用的「仅当被删区间最大值等于全局最大值时才全量重算」的策略，最坏场景下的开销是O(n)：比如每次删除的都是当前全局最大值对应的点，就会触发每次全量遍历的逻辑，这种场景下是有可感知延迟的
• 上面提到的分块方案，哪怕遇到最坏场景（每次删除的都是全局最大值所在的点），也只需要重算那个最大值所在的小块（几百个点以内），再更新全局的最大值计数，根本不会触发全量遍历，实际平均开销比你现有方案低几个数量级
• 你之前担心的「删除操作改变索引位置导致需要重算所有索引」的问题，本质是默认需要维护全局固定的物理索引映射——实际上因为你的删除操作都是基于有效点的顺序位置，而不是内存物理偏移，只要动态累计每个块的有效点数，就不需要做任何全量的索引重排操作

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