用段树查找给定数组中最大的一笔子阵 [英] Find the largest sum subarray from the given array using segment trees
问题描述
我想找到从给定数组中最大的一笔连续的子阵。我知道发现使用动态规划的使用Kadane算法的概念,最大的一笔连续的子阵方法的O(n)的方法。
但是,这需要大量的时间,如果没有一系列的问题都非常大。有没有办法用段树,因为它是pferred回答它解决了O(日志(n))的时间段查询的最佳选择$ P $来解决它。 谢谢你。
据我的意见,以贾斯汀的回答,您可以增加一个标准的线段树,实现了 O(日志(N))
带O的查询时间(n日志(n))的时间来建立树即插入所有n个元素放到树上。
我们的想法是存储在每个节点 v
不只是一个值,而是三个:
- MAX_VALUE [V]:=最大连续总和在v`s子树
- left_value [V]:=毗邻左侧的约束对应于V的子树范围最大连续总和
- right_value [V]:=毗邻必然对应于V的子树范围的右边
最大持续总和
为了执行更新操作的节点 v
,你必须重新计算 MAX_VALUE [V],left_value [V],right_value [ V]
。这是非常简单的,我想你自己看着办吧自己 - 有一些情况需要考虑
一个查询操作是在一个基本区段树相似于查询操作。唯一的区别是,在这种情况下,你也必须在 left_value [V]
和 right_value [V]
当计算结果 - 再次,有一些简单的情况下,考虑
我希望你会找出ommited细节。如果没有,让我知道,我会给出更详细的解释。
I wanted to find the largest sum continuous subarray from the given array. I know the O(n) approach of finding the largest sum continuous subarray approach using the concept of dynamic programming using Kadane's algorithm.
But it will take a lot of time if the no of range queries are very large. Is there a way to solve it using Segment-Trees as it is the best option preferred to answer range queries which it solves in O(log(n)) time. Thank you.
According to my comment to Justin's answer, you can augment a standard segment tree to achieve a O(log(n))
query time with O(n log(n)) time to build the tree i.e. to insert all n elements into the tree.
The idea is to store in every node v
not just one value, but three:
- max_value[v] := maximum continuous sum in v`s subtree
- left_value[v] := maximum continuous sum adjacent to the left bound of range corresponding to v's subtree
- right_value[v] := maximum continuous sum adjacent to the right bound of range corresponding to v's subtree
In order to perform an update operation for a node v
, you have to recompute max_value[v], left_value[v], right_value[v]
. This is very straightforward and I think you can figure it out by yourself - there are a few cases to consider.
A query operation is similar to a query operation in a basic segment tree. The only difference is that in this case, you have to consider also the left_value[v]
and the right_value[v]
while computing a result - again, there are a few easy cases to consider.
I hope that you'll figure out ommited details. If not, let me know and I'll give a more detailed explanation.
这篇关于用段树查找给定数组中最大的一笔子阵的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!