SPOJ你能回答这些问题吗？
我试图在SPOJ上解决这个问题。 我在段树部分发现了这个问题，所以我很确定可能有一些使用段树的可能解决方案。 但是我无法提出应该存储在树节点中的元数据。 可以使用Kadane的Algo计算最大总和。 但是如何使用分段树来计算它。 如果我们只存储algo的输出，该范围对于该特定范围的查询是正确的，但父母使用该值是不正确的。 如果我们存储更多信息，如负和前缀以及负和后缀。 我能够解决一些测试用例。 但它并不完全正确。 请提供一些指示，说明如何处理元数据以解决此特定问题。 谢谢你的帮助。
您可以通过在前缀sums上构建分段树来解决它
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字段为您提供相关间隔中最大总和子数组的总和。 这是两个子节点中的最大和子数组之一，或者是跨越两个子区间的序列，这是通过从右子项中的最大值减去左子项中的最小值得到的，我们也在可能的线性解：找到每个i的最小sum[j], j < i i ，然后将sum[i] - sum[j]与全局max进行比较。
现在，要回答查询，您需要考虑其关联间隔构成查询间隔的节点，并执行类似于我们构建树的方法。 您应该尝试自己解决这个问题，但如果您遇到困难，请告诉我。