Как предлагает Макдауэлла в их ответе, пусть K2 = K/2, округляя, и пусть M-наименьшая степень 2, то есть >= K2. Перспективным подходом был бы поиск смежных блоков нулей K2, полностью содержащихся в одном блоке размера M, и как только мы их найдем, проверьте соседние блоки размера M, чтобы увидеть, содержат ли они достаточное количество соседних нулей. Для начального сканирования, если число 0s в блоке = K2 и размер блока блок - это >= 2*M, мы можем посмотреть на оба подблока.

Это предполагает следующий код. Ниже, A[0 .. N-1] является массивом деревьев Фенвика; N считается степенью 2. Я предполагаю, что вы считаете пустые слоты, а не непустые; если вы предпочитаете считать пустые слоты, достаточно легко перейти от одного к другому.

initialize q as a stack data structure of triples of integers
push (N-1, N, A[n-1]) onto q
# An entry (i, j, z) represents the block [i-j+1 .. i] of length j, which
# contains z zeroes; we start with one block representing the whole array.
# We maintain the invariant that i always has at least as many trailing ones
# in its binary representation as j has trailing zeroes. (**)
initialize r as an empty list of pairs of integers
while q is not empty:
    pop an entry (i,j,z) off q
    if z < K2:
        next

    if FW(i) >= K:
        first_half := i - j/2
        # change this if you want to count nonempty slots:
        first_half_zeroes := A[first_half]
        # Because of invariant (**) above, first_half always has exactly
        # the right number of trailing 1 bits in its binary representation
        # that A[first_half] counts elements of the interval
        # [i-j+1 .. first_half].

        push (i, j/2, z - first_half_zeroes) onto q
        push (first_half, j/2, first_half_zeroes) onto q
    else:
        process_block(i, j, z)

Это позволяет нам обрабатывать все блоки размера M с по крайней мере K / 2 нулями по порядку. Вы могли бы даже рандомизировать порядок, в котором вы нажимаете первый и вторая половина на q, чтобы получить блоки в случайном порядке, что может быть полезно для борьбы с ситуацией, когда первая половина вашего массива заполняется гораздо быстрее, чем вторая половина.

Теперь нам нужно обсудить, как обрабатывать один блок. Если z = j, то блок полностью заполнен нулями, и мы можем смотреть как влево, так и вправо, чтобы добавить нули. В противном случае нам нужно выяснить, начинается ли он с >= K/2 непрерывных нулей, и если да, то с сколькими именно, а затем проверить, если предыдущий блок заканчивается подходящим количеством нулей. Аналогично, мы проверяем, заканчивается ли блок >= K/2 непрерывными нулями, и если да, то сколько именно, а затем проверяем, начинается ли следующий блок с подходящего числа нулей. Итак, нам понадобится процедура, чтобы найти количество нулей блока начинается или заканчивается, возможно с ярлыка, если это не менее или более B. Чтобы быть точным: пусть ends_with_zeroes(я, J, мин, макс) быть процедура, которая возвращает количество нулей, что блок из [i-j+1 .. j] заканчивается, с ярлыком для возврата max, если результат будет больше max и min, если результат будет меньше min. Аналогично для starts_with_zeroes (i, j, min, max).

def process_block(i, j, z):
    if j == z:
        if i > j:
            a := ends_with_zeroes(i-j, j, 0, K-z)
        else:
            a := 0

        if i < N-1:
            b := starts_with_zeroes(i+j, j, K-z-a-1, K-z-a)
        else:
            b := 0

        if b >= K-z-a:
            print "Found: starting at ", i - j - a + 1
        return

    # If the block doesn't start or end with K2 zeroes but overlaps with a
    # correct solution anyway, we don't need to find it here -- we'll find it
    # starting from the adjacent block.
    a := starts_with_zeroes(i, j, K2-1, j)
    if i > j and a >= K2:
        b := ends_with_zeroes(i-j, j, K-a-1, K-a)
        if b >= K-a:
            print "Found: starting at ", i - j - a + 1
        # Since z < 2*K2, and j != z, we know this block doesn't end with K2
        # zeroes, so we can safely return.
        return

    a := ends_with_zeroes(i, j, K2-1, j)
    if i < N-1 and a >= K2:
        b := starts_with_zeroes(i+j, K-a-1, K-a)
        if b >= K-a:
            print "Found: starting at ", i - a + 1

Обратите внимание, что во втором случае, когда мы находим решение, может быть возможно переместить начальную точку влево немного дальше. Вы можете проверить это отдельно, если вам нужна самая первая позиция, с которой он может начать.

Теперь осталось только реализовать starts_with_zeroes и ends_with_zeroes. Для того, чтобы проверить, что блок начинается с как минимум мин нулей, мы можем проверить, что он начинается с 2^ч нулей (где 2^х = Макс короткий путь в другую сторону (за исключением, если Макс = J, это сложнее, чтобы найти правильный отсчет от Фенвик дерево); затем найдите точное количество.

def starts_with_zeroes(i, j, min, max):
    start := i-j

    h2 := 1
    while h2 * 2 <= min:
        h2 := h2 * 2
        if A[start + h2] < h2:
            return min
    # Now h2 = 2^h in the text.
    # If you insist, you can do the above operation faster with bit twiddling
    # to get the 2log of min (in which case, for more info google it).

    while h2 < max and A[start + 2*h2] == 2*h2:
        h2 := 2*h2
    if h2 == j:
        # Walk up the Fenwick tree to determine the exact number of zeroes
        # in interval [start+1 .. i]. (Not implemented, but easy.) Let this
        # number be z.

        if z < j:
            h2 := h2 / 2

    if h2 >= max:
        return max

    # Now we know that [start+1 .. start+h2] is all zeroes, but somewhere in 
    # [start+h2+1 .. start+2*h2] there is a one.
    # Maintain invariant: the interval [start+1 .. start+h2] is all zeroes,
    # and there is a one in [start+h2+1 .. start+h2+step].
    step := h2;
    while step > 1:
        step := step / 2
        if A[start + h2 + step] == step:
             h2 := h2 + step
    return h2

Как вы видите, starts_with_zeroes довольно снизу вверх. Для ends_with_zeroes, я думаю вы бы хотели сделать более нисходящий подход, так как исследовать вторую половину чего-то в дереве Фенвика немного сложнее. Вы должны быть в состоянии выполнить аналогичный тип итерации в стиле бинарного поиска.

Этот алгоритм определенно не O (log (N)), и у меня есть предчувствие, что это неизбежно. Дерево Фенвика просто не дает информации, которая настолько хороша для вашего вопроса. Тем не менее, я думаю, что этот алгоритм будет работать довольно хорошо на практике, если подходящие интервалы достаточно велики. общий.

Одна быстрая проверка, при поиске диапазона K смежных слотов, заключается в нахождении наибольшей мощности из двух меньших или равных K / 2. Любые K непрерывных нулевых слотов должны содержать по крайней мере один выровненный по Фенвику диапазон слотов размером

В вашем примере самый низкий уровень содержит 0s или 1s, а верхний уровень содержит суммы потомков. Найти отрезки 0s было бы проще, если бы нижний уровень содержал 0s, где вы в данный момент записываете 1s, и подсчет количества смежных нулей слева, где вы в данный момент записываете нули, а верхние уровни содержали максимальное значение любого потомка. Обновление будет означать больше работы, особенно если у вас есть длинные строки нулей, которые создаются и уничтожаются, но вы можете найти самую левую строку нулей длина не менее K с одним поиском слева ветвление влево, где максимальное значение было не менее K. На самом деле здесь много работы по обновлению делается создание и уничтожение запусков 1,2,3,4... на самом нижнем уровне. Возможно, если вы оставите самый нижний уровень, как он был изначально определен, и проведете анализ последствий изменений от случая к случаю, вы сможете получить верхние уровни, отображающие самую длинную полосу нулей, начиная с любого потомка данного узла - для быстрого поиска - и получить разумное обновление стоимость.

@Erik описал разумный алгоритм зондирования. Однако обратите внимание, что эта задача имеет более низкую границу сложности Ω(N/K) в худшем случае.

Доказательство:

Рассмотрим сокращенную версию задачи, где:

• N и K являются степенями 2
• N > 2K >= 4

Предположим, что ваш входной массив состоит из (N/2K) фрагментов размером 2K. один фрагмент имеет вид K 0s, за которым следует K 1s, каждый второй фрагмент представляет собой строку "10", повторенную K раз. Есть (N / 2K) такие массивы, каждый из которых содержит ровно одно решение задачи (начало одного "специального" блока).

Пусть n = log2(N), k = log2 (K). Давайте также определим корневой узел дерева как находящийся на уровне 0, а листовые узлы как находящиеся на уровне n дерева.

Обратите внимание, что из-за того, что наш массив состоит из выровненных кусков размером 2K, уровень n-k дерева просто будет состоять из числа 1s в каждом куске. Тем не менее, каждый из наших блоков имеет одинаковое число 1s в нем. Это средство что каждый узел на уровне n-k будет идентичен, что в свою очередь означает, что каждый узел на уровне

Это означает, что дерево не содержит никакой информации, которая может устранить неоднозначность "специального" фрагмента, пока вы не начнете анализировать уровень n-k+1 и ниже. Но поскольку все узлы (N/K) на этом уровне, кроме 2, идентичны, это означает, что в худшем случае вам придется изучить O(N/K) узлов, чтобы отличить решение от остальных узлов.