c - SPOJ 你能回答这些问题吗？

Question

我试图在SPOJ上解决这个问题。我在段树部分发现了这个问题，所以我很确定可能有一些使用段树的可能解决方案。但我无法想出应该存储在树节点中的元数据。可以使用Kadane 的算法计算最大和. 但是如何使用线段树来计算。如果我们只存储一个范围的算法输出，该范围对于查询该特定范围是正确的，但对于父母使用该值是不正确的。如果我们存储更多信息，例如负和前缀以及负和后缀。我能够解决一些测试用例。但它并不完全正确。请提供一些关于我应该如何处理元数据来解决这个特定问题的指示。感谢您的帮助。

Answer 1

您可以通过在前缀和上构建分段树来解决它

sum[i] = sum[i - 1] + a[i] 

然后将以下信息保存在节点中：

node.min   = the minimum sum[i], x <= i <= y 
            ([x, y] being the interval associated to node)
           = minimum(node.left.min, node.right.min)
node.max   = same but with maximum

node.best  = maximum(node.left.best,
                     node.right.best,
                     node.right.max - node.left.min
                    )

基本上，该best字段为您提供相关区间中最大和子数组的总和。这是两个子节点中的最大和子数组之一，或者是跨越两个子区间的序列，这是通过从右孩子的最大值中减去左孩子的最小值获得的，我们也在一个可能的线性解决方案：找到sum[j], j < i每个 each的最小值i，然后sum[i] - sum[j]与全局最大值进行比较。

现在，要回答查询，您需要考虑其关联区间构成查询区间的节点，并执行与我们构建树的方式类似的操作。您应该尝试自己解决，但如果您在某个地方卡住了，请告诉我。