SPOJ你能回答这些疑问我 [英] SPOJ Can you answer these queries I

问题描述

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

I am trying to solve this problem on SPOJ. I found this problem in the segment tree section, so I am pretty sure that there could be some possible solution that uses segment tree. But I am unable to come up with the metadata that should be stored in the tree node. The maximum sum can be computed using Kadane's Algo. But how to compute that using segment tree. If we store just the output of algo for a range that would be correct for query for that particular range, but would be incorrect for parents to use that value. If we store some more information like negative sum prefix as well as negative sum suffix. I am able to solve some of the test cases. But its not completely correct. Please provide me some pointers as to how should I approach the metadata for solving this particular problem. Thanks for helping.

推荐答案

您可以通过在preFIX款项构建线段树解决

You can solve it by building a segment tree on the prefix sums

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

然后保持下列信息中的一个节点：

and then keeping the following information in a node:

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
                    )

基本上，最佳字段为您提供了最大总和子阵列相关区间的总和。这是在两个子节点的任一个的最大总和子阵列，或一个序列跨越两个子间隔，它是由减去最小的左子从最大的右子获得的，这是我们还做了一个可能的线性解决方案：找到最小总和[J]，J＆LT;我每个每个我，然后比较总和[I] - 总和[J] 与全球最大

Basically, the best field gives you the sum of the maximum sum subarray in the associated interval. This is either one of the maximum sum subarrays in the two child nodes, or a sequence that crosses both of the child intervals, which is obtained by subtracting the minimum in the left child from the maximum in the right child, which we also do in a possible linear solution: find the minimum sum[j], j < i for each each i, then compare sum[i] - sum[j] with the global max.

现在，来回答你需要考虑，其相关的间隔使你的查询时间，做类似我们如何建造的树一些节点的查询。你应该揣摩出你自己的，但让我知道如果你得到的地方卡住了。

Now, to answer a query you will need to consider the nodes whose associated intervals make up your queried interval and do something similar to how we built the tree. You should try to figure it out on your own, but let me know if you get stuck somewhere.

这篇关于SPOJ你能回答这些疑问我的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！