我想找到从给定数组中最大的一笔连续的子阵。我知道发现使用动态规划的使用Kadane算法的概念,最大的一笔连续的子阵方法的O(n)的方法。
但是,这需要大量的时间,如果没有一系列的问题都非常大。有没有办法用段树,因为它是pferred回答它解决了O(日志(n))的时间段查询的最佳选择$ P $来解决它。 谢谢你。
解决方案据我的意见,以贾斯汀的回答,您可以增加一个标准的线段树,实现了 O(日志(N))
带O的查询时间(n日志(n))的时间来建立树即插入所有n个元素放到树上。
我们的想法是存储在每个节点 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:
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.
相关推荐
最新文章