c++ - 如何使用段树查找数组中的前 2 个最小整数

Question

如何找到前两个最小元素来询问和更新它。

在我看来，我必须使用分段（segment-tree）

标签： c++algorithmsegment-tree

Answer 1

这可以通过对 RMQ 段树的简单修改来解决

这是 O(N log N) 方法：

1. 为给定数组构建段树
2. 对于分段树中的每个节点，存储当前范围及其索引的最小值
3. 处理类型 1 的查询如下：
   • 查找范围 [L,R] 及其索引中的最小值
   • 在 [L, found_index-1] 和 [found_index+1, R] 范围内查找最小值
4. 对于类型 2 的查询，只需更新段树