使用分段树从给定数组中找出最大的和子数组

Answer 1

根据我对Justin答案的评论，您可以增加一个标准段树，以实现O(log(n))查询时间，并使用O(n log(n))构建树的时间，即将所有n个元素插入到树中。

其思想是在每个节点v中不仅存储一个值，还存储四个值：

1. max_value[v]:=v`s子树中的最大连续和
2. left_value[v]:=与v的子树对应的值域左界相邻的最大连续和
3. right_value[v]:=与v的子树对应的值域右界相邻的最大连续和
4. sum[v]:=v的子树中所有元素的和

为了对节点v执行更新操作，必须重新计算max_value[v]、left_value[v]、right_value[v]、sum[v]。这很简单，我想你可以自己弄明白--有几种情况需要考虑。

查询操作类似于基本段树中的查询操作。唯一的区别是，在本例中，在计算结果时还必须考虑left_value[v]和right_value[v]-同样，还有一些容易考虑的情况。

我希望你能找出省略的细节。如果没有，让我知道，我会给更详细的解释。