相关疑难解决方法(0)

Fenwick树是一种数据结构,可以有效地回答主要查询:

• 将元素添加到数组的特定索引 update(index, value)
• 找到从1到N的元素总和 find(n)

两个操作都O(log(n))及时完成,我理解逻辑和实现.实现一堆其他操作并不难,比如找到从N到M的总和.

我想了解如何使Fenwick树适应RMQ.很明显,改变Fenwick树的前两个操作.但我没有弄清楚如何在从N到M的范围内找到最小值.

在寻找解决方案之后,大多数人认为这是不可能的,并且少数人声称它实际上可以完成(方法1,方法2).

第一种方法(用我的谷歌翻译写的俄语有0个解释,只有两个函数)依赖于三个数组(初始,左和右),因为我的测试对所有可能的测试用例都没有正常工作.

第二种方法只需要一个阵列,并且基于声明的运行,O(log^2(n))并且几乎没有解释为什么以及如何工作.我没有试过测试它.

鉴于有争议的主张,我想知道是否有可能增加Fenwick树来回答update(index, value)和findMin(from, to).

如果有可能,我会很高兴听到它是如何运作的.