给定一个二进制数组(元素为0或1),我需要在数组中给定的范围(l和r)内找到所有为1的最大子数组的长度。
我知道使用O(n)方法可以找到这样的子数组,但如果有O(n)个查询,则总复杂度将变为O(n²)。
我知道线段树用于此类问题,但我无法想出如何构建此问题的树。
我是否可以构建一个线段树,在log(n)时间内回答查询,以使对于O(n)个查询的总体复杂度变为O(nlog(n))。
给定一个二进制数组(元素为0或1),我需要在数组中给定的范围(l和r)内找到所有为1的最大子数组的长度。
我知道使用O(n)方法可以找到这样的子数组,但如果有O(n)个查询,则总复杂度将变为O(n²)。
我知道线段树用于此类问题,但我无法想出如何构建此问题的树。
我是否可以构建一个线段树,在log(n)时间内回答查询,以使对于O(n)个查询的总体复杂度变为O(nlog(n))。
假设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
的长度。M
不是 N/2
吗?所有查询的最坏情况复杂度仍然为 O(N^2)。 - merlynN
值很大的情况下也比任何基于树的解决方案快得多(但我猜不是渐近意义上的)。 - Nelfeal是的,您可以使用线段树来解决这个问题。
让我们尝试思考一下这棵树应该是什么样子的。显然,每个节点都必须包含该范围内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]
中,我们可以维护左和右的和数组。从左到右的左和数组为 [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_devmax(left,right,left_sum[R]-left_sum[L-1] + right_sum[R] - right_sum[L-1])
。请注意,由于 right_sum
是从右到左的,因此需要相应地调整 R
和 L
的值。 - nice_devL
和 R
。抱歉,我应该提到它,下一个更高层级将是 mid
。 - nice_dev
O(n)
查询是什么意思?你真的想要按照长度递减的顺序构建子数组列表吗? - NelfealO(n^2)
? - NelfealL
和R
,使得 [L;R] 是最大长度的子数组。” - Nelfeal