我正在尝试解决SPOJ上的这个问题。我在段树部分中发现了此问题，因此我很确定可能存在一些使用段树的解决方案。但是我无法提出应存储在树节点中的元数据。可以使用Kadane的算法来计算最大和。但是如何使用段树来计算。如果我们仅将算法的输出存储在某个范围内，该范围对于该特定范围的查询将是正确的，但对于父母使用该值将是不正确的。如果我们存储更多信息，例如负和前缀以及负和后缀。我能够解决一些测试用例。但是它并不完全正确。请提供一些有关如何使用元数据来解决此特定问题的指示。感谢您的帮助。
您可以通过在前缀和上构建段树来解决它
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]与全局最大值进行比较。
best
sum[j], j < i
i
sum[i] - sum[j]
现在，要回答查询，您将需要考虑其关联间隔构成您查询间隔的节点，并执行与构建树类似的操作。您应该尝试自己解决问题，但是如果您遇到问题，请告诉我。
