use*_*096 11 arrays algorithm segment-tree
我想找到给定数组中最大的和连续子数组.我知道使用Kadane算法使用动态规划的概念找到最大和连续子阵列方法的O(n)方法.
但是如果范围查询的数量非常大,则需要花费很多时间.有没有办法使用Segment-Trees来解决它,因为它是在O(log(n))时间内解决范围查询的首选方案.谢谢.
根据我对Justin的回答的评论,你可以扩充一个标准的段树来实现一个O(log(n))查询O(n log(n))时间来构建树,即将所有n个元素插入到树中.
我们的想法是在每个节点中存储的v不仅仅是一个值,而是四个:
- max_value [v]:= v`s子树中的最大连续和
- left_value [v]:=与v的子树对应的范围的左边界附近的最大连续和
- right_value [v]:=与v的子树对应的范围的右边界附近的最大连续和
- sum [v]:= v子树中所有元素的总和
要为节点执行更新操作v,必须重新计算max_value[v], left_value[v], right_value[v], sum[v].这非常简单,我认为你可以自己解决这个问题 - 有几个案例需要考虑.
查询操作类似于基本段树中的查询操作.唯一的区别是,在这种情况下,你还必须考虑left_value[v]和right_value[v]计算结果的同时 - 再次,有一些容易考虑的案例.
我希望你能算出遗漏的细节.如果没有,请告诉我,我会给出更详细的解释.