寻找通过数组的最低价格的算法
Algorithm for finding the lowest price to get through an array
我一直在思考以下问题：
我们得到了一个包含 n 个数字的数组。我们从第一个索引开始，我们的任务是到达最后一个索引。每一步我们都可以向前跳一两步，我们跳到的索引处的数字代表我们访问该索引所需支付的成本。我们需要找到到达数组末尾的最便宜的方法。
例如，如果数组如下所示：[2,1,4,2,5] 最便宜的方法是 10：我们访问索引1->2->4->5 我们必须支付 2+1+2+5 = 10 这是最便宜的方式.设 f(i) 是达到指数 i 的最便宜价格。通过实现 f(i) = arr[i] + min(f(i-1) ,f(i-2))
但问题在于：
该数组会更新多次，每次更新后，我们需要能够在 O(logn) 时间内告诉我们目前最便宜的方法是什么。通过告知将更改的索引以及将更改为的数字来更新数组。例如，更新可以是 arr[2] = 7 将我们的示例数组更改为 [2,7,4,2,5]。现在最便宜的方式是 11。
现在我们如何在 O(logn) 时间内支持这些更新？有什么想法吗？
这是我到目前为止的想法：
首先，我会为前面描述的动态规划创建一个数组 f。我将按以下方式将此数组的内容存储在线段树 s 中：s(i) = f(i) - f(i-1)。这将允许我在 O(logn) 时间内更新 f 的间隔（为每个值添加一个常量）并在在 O(logn) 时间内给定索引。这会很方便，因为在一些更新之后，经常会发生 f 中的所有值都需要在 f[=56= 中的某个给定索引之后增加一个常数].因此，通过在每次更新后在线段树中询问 s(n) 的值，我们将得到我们需要的答案。
然而，更新后可能会发生不同的事情：
- f中只有一个值需要更新。例如，如果 [2,1,4,2,5,4,9,3,7] 更改为 [2,1,9,2,5 ,4,9,3,7] 只有 f(3) 需要更新，因为无论如何都没有最便宜的方式通过 3. 索引。
- f中给定索引之后的所有值都需要用常量更新。这就是线段树的用处。
- f 中给定索引之后的每个其他值都需要用常量更新。
- 更随机的东西。
好吧，我自己设法解决了这个问题，所以我决定与您分享解决方案。 :)
我在动态规划和线段树方面走在了正确的轨道上，但在我之前的尝试中我以错误的方式喂养线段树。
以下是我们如何在 O(logn) 时间内支持更新：
这个想法是使用二叉树，其中树的叶子代表当前数组，每个节点存储 4 个不同的值。
- v1 = 从最左边的后代到最右边的后代的最低成本
- v2 = 从最左边的后代到第二个最右边的后代的最低成本
- v3 = 从第二个最左边的后代到最右边的后代的最低成本
- v4 = 从第二个最左后代到第二个最右后代的最低成本
对于后代，我的意思是节点的后代也是叶子。
更新数组时，我们更新叶节点的值，然后更新其所有祖先节点，直至根节点。由于在每个节点上我们都已经知道其两个子节点的所有这 4 个值，因此我们可以轻松计算当前父节点的新 4 个值。举个例子：v1_current_node = min(v2_leftchild+v1_rightchild, v1_leftchild+v1_rightchild, v1_leftchild+v3_rightchild)。所有其他三个值都可以用类似的方式计算。
因为每片叶子只有O(logn)个祖先，所有4个值都是在O(1)时间内计算出来的更新整个树只需要 O(logn) 时间。
既然我们知道每个节点的4值，我们可以用类似的方式计算从第一个到n[=48个的最低成本=]:th 节点，使用树中路径中 2 的最高幂的节点，加起来为 n。例如，如果 n = 11 我们想知道从第一个节点到第十一个节点的最低成本，这可以通过使用覆盖叶子 1 的节点的信息来完成-8，覆盖叶子9-10和叶子节点11的节点。对于所有这三个节点，我们知道所描述的 4 值，我们可以以类似的方式组合该信息来找出答案。最多我们需要考虑 O(logn) 个节点来执行此操作，所以这不是问题。
我一直在思考以下问题：
我们得到了一个包含 n 个数字的数组。我们从第一个索引开始，我们的任务是到达最后一个索引。每一步我们都可以向前跳一两步，我们跳到的索引处的数字代表我们访问该索引所需支付的成本。我们需要找到到达数组末尾的最便宜的方法。
例如，如果数组如下所示：[2,1,4,2,5] 最便宜的方法是 10：我们访问索引1->2->4->5 我们必须支付 2+1+2+5 = 10 这是最便宜的方式.设 f(i) 是达到指数 i 的最便宜价格。通过实现 f(i) = arr[i] + min(f(i-1) ,f(i-2))
但问题在于： 该数组会更新多次，每次更新后，我们需要能够在 O(logn) 时间内告诉我们目前最便宜的方法是什么。通过告知将更改的索引以及将更改为的数字来更新数组。例如，更新可以是 arr[2] = 7 将我们的示例数组更改为 [2,7,4,2,5]。现在最便宜的方式是 11。
现在我们如何在 O(logn) 时间内支持这些更新？有什么想法吗？
这是我到目前为止的想法： 首先，我会为前面描述的动态规划创建一个数组 f。我将按以下方式将此数组的内容存储在线段树 s 中：s(i) = f(i) - f(i-1)。这将允许我在 O(logn) 时间内更新 f 的间隔（为每个值添加一个常量）并在在 O(logn) 时间内给定索引。这会很方便，因为在一些更新之后，经常会发生 f 中的所有值都需要在 f[=56= 中的某个给定索引之后增加一个常数].因此，通过在每次更新后在线段树中询问 s(n) 的值，我们将得到我们需要的答案。
然而，更新后可能会发生不同的事情：
- f中只有一个值需要更新。例如，如果 [2,1,4,2,5,4,9,3,7] 更改为 [2,1,9,2,5 ,4,9,3,7] 只有 f(3) 需要更新，因为无论如何都没有最便宜的方式通过 3. 索引。
- f中给定索引之后的所有值都需要用常量更新。这就是线段树的用处。
- f 中给定索引之后的每个其他值都需要用常量更新。
- 更随机的东西。
好吧，我自己设法解决了这个问题，所以我决定与您分享解决方案。 :)
我在动态规划和线段树方面走在了正确的轨道上，但在我之前的尝试中我以错误的方式喂养线段树。
以下是我们如何在 O(logn) 时间内支持更新： 这个想法是使用二叉树，其中树的叶子代表当前数组，每个节点存储 4 个不同的值。
- v1 = 从最左边的后代到最右边的后代的最低成本
- v2 = 从最左边的后代到第二个最右边的后代的最低成本
- v3 = 从第二个最左边的后代到最右边的后代的最低成本
- v4 = 从第二个最左后代到第二个最右后代的最低成本
对于后代，我的意思是节点的后代也是叶子。
更新数组时，我们更新叶节点的值，然后更新其所有祖先节点，直至根节点。由于在每个节点上我们都已经知道其两个子节点的所有这 4 个值，因此我们可以轻松计算当前父节点的新 4 个值。举个例子：v1_current_node = min(v2_leftchild+v1_rightchild, v1_leftchild+v1_rightchild, v1_leftchild+v3_rightchild)。所有其他三个值都可以用类似的方式计算。
因为每片叶子只有O(logn)个祖先，所有4个值都是在O(1)时间内计算出来的更新整个树只需要 O(logn) 时间。
既然我们知道每个节点的4值，我们可以用类似的方式计算从第一个到n[=48个的最低成本=]:th 节点，使用树中路径中 2 的最高幂的节点，加起来为 n。例如，如果 n = 11 我们想知道从第一个节点到第十一个节点的最低成本，这可以通过使用覆盖叶子 1 的节点的信息来完成-8，覆盖叶子9-10和叶子节点11的节点。对于所有这三个节点，我们知道所描述的 4 值，我们可以以类似的方式组合该信息来找出答案。最多我们需要考虑 O(logn) 个节点来执行此操作，所以这不是问题。