tyk*_*eli 6 arrays algorithm dynamic-programming data-structures segment-tree
我一直在考虑以下问题:
我们给出了一组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(n)时间内通过动态编程 轻松计算
但是这里有一个转折点:数组会多次更新,每次更新后我们都需要能够在O(logn)时间告诉我目前最便宜的方式.通过告知将要更改的索引以及将更改为的数字来更新数组.例如,更新可能是arr [2] = 7将我们的示例数组更改为[2,7,4,2,5].现在最便宜的方式是11.
现在我们如何在O(logn)时间内支持这些更新？有任何想法吗？
这是我到目前为止所提出的:首先,我将为之前描述的动态编程创建一个数组f.我将以下列方式将该数组的内容存储在段树s中:s(i)= f(i)-f(i-1).这将使我更新的间隔˚F中(加上一个常数,以每一个值)O(LOGN)时间,在给定的索引处索要值O(LOGN)的时间.这会很方便,因为在经过一些更新之后,经常发生f中的所有值需要在f中的某个给定索引之后增加一个常量.因此,通过在每次更新后询问段树中的s(n)的值,我们将得到我们需要的答案.
然而,更新后可能会发生不同的事情:
好吧，我自己解决了这个问题，所以我决定与你分享解决方案。:)
我在动态编程和线段树方面走在正确的轨道上，但在之前的尝试中，我以错误的方式提供了线段树。
以下是我们如何支持O(logn)时间内的更新：这个想法是使用二叉线段树，其中树的叶子代表当前数组，每个节点存储 4 个不同的值。
对于后代，我指的是节点的后代，它们也是叶子。
更新数组时，我们更新叶子处的值，然后更新其所有祖先直到根部。由于在每个节点上我们已经知道其两个子节点的所有这 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个节点的最低成本，方法是使用树中路径中2的最高幂的节点，总计为名词 例如，如果n = 11，我们想知道从第一个到第十一个节点的最低成本，这可以通过使用覆盖叶子1-8 的节点、覆盖叶子9-10的节点和叶子的信息来完成节点11。对于所有这三个节点，我们知道所描述的4 个值，并且我们可以以类似的方式组合这些信息来找出答案。我们最多需要考虑O(logn)个节点来执行此操作，因此这不是问题。