SPOJ 你能回答这些问题吗？

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

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

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对于每一个i，然后比较sum[i] - sum[j]与全球最大。

现在，要回答查询，您需要考虑其关联间隔构成查询间隔的节点，并执行类似于我们构建树的方式的操作。您应该尝试自己解决这个问题，但如果您遇到困难，请告诉我。