我在数据结构课程中进行了测试，其中一个问题是：
假设您有一个 n 大小的数组，该数组由 Range Minimum Query 维护，该查询给出了 o(1) 复杂度的数组中两个数字之间的最小值。当然，该数组是 o(n) 准备使用动态编程针对不同选项来回答 RMQ 的。问题是 - 如果我更改数组中的一个对象（数字），我将如何更改我所做的准备工作以便我仍然可以在 o(1) 中找到 RMQ，以及它需要什么复杂性。
答案不是在 o(n) 中创建一个新的 RMQ，它必须小于这个值。
这个问题不是作业，我只是想通过测试来理解。
提前致谢。
存储索引 I 和更改的元素的新值 V。
在获取查询 [L,R] 时，检查 L <= I <= R，如果是，则返回 old_rmq(L,R) 和 V 的最小值。
RMQ根据 和 的复杂度，update实际上存在三种类型的算法query：
Update Query
1. O(N) O(1)
2. O(1) O(N)
3. O(logN) O(logN)
第一类和第二类算法实现起来非常简单。第一个涉及存储所有可能查询的值，从而O(1)及时回答它们。第二个只涉及及时更新数据结构O(1)，但查询需要O(N). 根据您的问题，不可能有这样的组合。
然而，第三种算法特别令人感兴趣。如果您放宽查询可能需要O(logN)时间而不是的条件O(1)，您还将拥有一个优势，即无论更新和查询的数量如何，总体运行时间都保持不变。