给定一个二进制数组（元素为0或1），我需要在数组中给定的范围（l和r）内找到所有为1的最大子数组的长度。
我知道使用O(n)方法可以找到这样的子数组，但如果有O(n)个查询，则总复杂度将变为O(n²)。
我知道线段树用于此类问题，但我无法想出如何构建此问题的树。
我是否可以构建一个线段树，在log(n)时间内回答查询，以使对于O(n)个查询的总体复杂度变为O(nlog(n))。
2个回答
1
假设A是您的二进制数组。
构建两个数组IL和IR:
- IL按顺序包含每个i，使得A[i] = 1 and (i = 0 or A[i-1] = 0);
- IR按顺序包含每个i，使得A[i-1] = 1 and (i = N or A[i] = 0)。
换句话说，对于任何i，由IL[i]（包括）和IR[i]（不包括）定义的范围对应于A中的一系列1。
{L，R}（包括[L;R]范围内的所有元素），让S = 0 。使用i遍历IL和IR，直到IL [i] >= L 为止。此时，如果IR [i-1] > L ，则将S = IR [i-1] -L 。继续遍历IL和IR，同时设置S = max（S，IR [i] -IL [i]），直到IR [i] > R 。最后，如果IL [i] <= R ，则设置S = max（S，R-IL [i]）。
S现在是A中在L和R之间的最大1序列的大小。
IL和IR的复杂度为O(N)，回答查询的复杂度为O(M)，其中M为IL或IR的长度。- Nelfeal
3
在最坏情况下，
M 不是 N/2 吗？所有查询的最坏情况复杂度仍然为 O(N^2)。 - merlyn在最坏情况下，M = N/4，但我猜平均情况下是O(log N)。 - Nelfeal
这真的取决于 OP 究竟想要什么，因为这种算法即使在
N 值很大的情况下也比任何基于树的解决方案快得多（但我猜不是渐近意义上的）。 - Nelfeal1
是的，您可以使用线段树来解决这个问题。
让我们尝试思考一下这棵树应该是什么样子的。显然，每个节点都必须包含该范围内1和0的最大子数组长度。
现在，我们如何将两个节点连接成一个更大的节点。换句话说，您有一个表示[low，mid）的节点和一个表示[mid，high）的节点。您必须获得[low，high)的最大子数组。 首先，整体的最大值至少为部分的最大值。因此，我们必须在左侧和右侧值中取最大值。
但是，如果真正的最大子数组重叠了两个节点怎么办？好吧，那么它必须是左节点的最右边部分和右节点的最左边部分。因此，我们还需要跟踪开头和结尾的最长子数组。
现在，如何更新这些最左边和最右边的子数组长度呢？好吧，父节点的最左边必须是左子节点的最左边，除非左子节点的最左边跨越了整个左节点。在这种情况下，父节点的最左边将是左+右节点的最左边。
类似的规则适用于跟踪1的最右边的子数组。
我们完成了。以下是伪代码中的最终规则。
max_sub[parent] = max(max_sub[left], max_sub[right], right_sub[left] + left_sub[right])
left_sub[parent] = left_sub[left] if left_sub[left] < length[left] else left_sub[left] + left_sub[right]
right_sub[parent] = right_sub[right] if right_sub[right] < length[right] else right_sub[right] + right_sub[left]
请注意，在查找范围的结果时，您需要采取类似的步骤。
以下是数组[0, 1, 1, 0, 1, 1, 1, 0]的示例树。
- merlyn
6
请添加一个图表以进行说明。 - nice_dev
1@vivek_23 我已经添加了一幅图。 - merlyn
我们可以简化计算。在
[0, 1, 1, 0, 1, 1, 1, 0] 中，我们可以维护左和右的和数组。从左到右的左和数组为 [0, 1, 2, 0, 1, 2, 3, 0]，从右到左的右和数组为 [0, 2, 1, 0, 3, 2, 1, 0]。棘手的部分是 重叠情况。我们可以利用这些数组来获取从左侧添加的 1 运行与从右侧添加的 1 运行。要从左和中获取范围 [L，R] 的 1 运行，则左侧和将为 left_sum [R] - left_sum [L-1]。右侧和也是如此。因此，我们不需要为每个节点维护 left 和 right，只需维护 max 即可。 - nice_dev现在，你可以将节点的最大值计算为
max(left,right,left_sum[R]-left_sum[L-1] + right_sum[R] - right_sum[L-1])。请注意，由于 right_sum 是从右到左的，因此需要相应地调整 R 和 L 的值。 - nice_dev1@vivek_23，我认为你的代码有误。你应该从中间取左侧运行，并从mid + 1取右侧运行，而不是L和R。但这个想法非常好。也许你应该再添加一个答案？ - merlyn
1是的，我指的是较低节点的
L 和 R。抱歉，我应该提到它，下一个更高层级将是 mid。 - nice_dev网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
O(n)查询是什么意思？你真的想要按照长度递减的顺序构建子数组列表吗？ - NelfealO(n^2)？ - NelfealL和R，使得 [L;R] 是最大长度的子数组。” - Nelfeal