我无法弄清楚如何以有效的方式解决以下链接中的问题 2： http ://www.iarcs.org.in/inoi/2012/inoi2012/inoi2012-qpaper.pdf
问问题
493 次
1 回答
2
您可以在 On log n) 时间内执行此操作。（如果你真的愿意，也可以是线性的。）首先，使用一些非常大的负数将输入数组填充到 2 的下一次幂。现在，构建一个区间树状数据结构；通过将数组分成两半来递归地对数组进行分区。树中的每个节点代表一个子数组，其长度是 2 的幂，并且从一个位置开始，该位置是其长度的倍数，并且每个非叶节点都有一个“左半边”子节点和一个“右半边”子节点。
计算，对于树中的每个节点，当您添加0,1,2,3,...到该子数组并获取最大元素时会发生什么。请注意，这对于代表长度为 1 的子数组的叶子来说是微不足道的。对于内部节点，这只是长度/2 + 右孩子的左孩子的最大值。所以你可以在线性时间内构建这棵树。
现在我们想在这棵树上运行一系列n查询并打印出答案。查询的形式是“如果我添加k,k+1,k+2,...n,1,...,k-1到数组并报告最大值会发生什么？”
请注意，当我们将该序列添加到整个数组时，n 和 1 之间的中断要么发生在开始/结束处，要么发生在中间，或者在左半部分的某个地方，或者在右半部分的某个地方。因此，将数组划分为k,k+1,k+2,...,n部分和1,2,...,k-1部分。如果您在树中识别出代表子数组的所有节点，这些子数组完全位于两个序列之一内，但其父节点不存在或跨越断点，您将拥有 O(log n) 个节点。您需要查看它们的值，添加各种常量并取最大值。所以每个查询都需要 O(log n) 时间。
于 2012-12-29T18:23:38.953 回答