Я думаю, что самый простой способ реализовать все желаемые функции с временной сложностью O (log N) и в то же время минимизировать требования к памяти — это использовать битовый вектор для хранения всех значений 0/1 (свободно/используется). Битовый вектор может заменить 6 нижних уровней как дерева Фенвика, так и дерева сегментов (если они реализованы как 64-битные целые числа). Таким образом, высота этих деревьев может быть уменьшена в 6 раз, а требуемое пространство для каждого из этих деревьев будет в 64 (или 32) раза меньше, чем обычно.

Дерево сегментов может быть реализовано как неявное двоичное дерево, находящееся в массиве (точно так же, как известная реализация max-heap). Корневой узел с индексом 1, каждый левый потомок узла с индексом i помещается в 2*i, каждый правый потомок - в 2*i+1. Это означает, что требуется в два раза больше места по сравнению с деревом Фенвика, но поскольку высота дерева урезана на 6 уровней, это не является большой проблемой.

Каждый узел дерева отрезков должен хранить единственное значение — длину самой длинной непрерывной последовательности «свободных» слотов, начинающихся в точке, охватываемой этим узлом (или ноль, если такой начальной точки нет). Это делает поиск первого диапазона заданного числа смежных нулей очень простым: начните с корня, затем выберите левого потомка, если он содержит значение, большее или равное требуемому, в противном случае выберите правого потомка. Придя к какому-то листовому узлу, проверить соответствующее слово битового вектора (на наличие нулей в середине слова).

Операции обновления более сложны. При изменении значения на «используемое» проверьте соответствующее слово битового вектора, если оно пусто, поднимитесь по дереву сегментов, чтобы найти ненулевое значение для некоторого левого потомка, затем спуститесь по дереву, чтобы добраться до самого правого листа с этим значением, затем определите, как вновь добавленный слот разбивает «свободный» интервал на две половины, затем обновляет все родительские узлы как для добавленного слота, так и для начального узла разбиваемого интервала, а также устанавливает бит в битовом векторе. Изменение значения на «бесплатно» может быть реализовано аналогичным образом.

Если также необходимо получить количество ненулевых элементов в некотором диапазоне, реализуйте дерево Фенвика над тем же битовым вектором (но отдельно от дерева сегментов). В реализации дерева Фенвика нет ничего особенного, за исключением того, что сложение 6 нижних узлов заменяется операцией «подсчет населения» для некоторого слова битового вектора. Пример использования дерева Фенвика вместе с битовым вектором см. в первом решении для Magic Board на CodeChef.

Все необходимые операции над битовым вектором можно довольно эффективно реализовать с помощью различных побитовых трюков. Для некоторых из них (число начальных/конечных нулей и количество населения) вы можете использовать либо встроенные функции компилятора, либо инструкции ассемблера (в зависимости от целевой архитектуры).

Если битовый вектор реализован с 64-битными словами, а узлы дерева - с 32-битными словами, то оба дерева занимают 150% пространства в дополнение к битовому вектору. Это может быть значительно уменьшено, если каждый листовой узел будет соответствовать не одному слову битового вектора, а небольшому диапазону (4 или 8 слов). Для 8 слов дополнительное пространство, необходимое для деревьев, составит всего 20% от размера битового вектора. Это несколько усложняет реализацию. При правильной оптимизации производительность должна быть примерно такой же, как и в варианте для одного слова на листовой узел. Для очень больших наборов данных производительность, вероятно, будет лучше (поскольку вычисления с битовыми векторами более удобны для кэширования, чем обход деревьев).

Как предлагает mcdowella в их ответе, пусть K2 = K/2, округляя вверх, и пусть M будет наименьшей степенью числа 2. то есть >= К2. Многообещающим подходом был бы поиск смежных блоков K2 нулей, полностью содержащихся в одном блоке размера M, и, как только мы их нашли, проверка соседних блоков размера M, чтобы увидеть, содержат ли они достаточное количество смежных нулей. Для начального сканирования, если количество нулей в блоке ‹ K2, очевидно, мы можем его пропустить, а если количество нулей >= 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 непрерывных нулей, и если да, то сколько именно, а затем проверяем, начинается ли следующий блок с подходящего количества нулей. Поэтому нам понадобится процедура для определения количества нулей, с которых начинается или заканчивается блок, возможно, с сокращением, если это не меньше a или не больше b. Чтобы быть точным: пусть end_with_zeroes(i, j, min, max) будет процедурой, которая возвращает количество нулей, которыми заканчивается блок из [i-j+1 .. j], с ярлыком для возврата max, если результат будет больше max и min, если результат будет меньше min. Аналогично для start_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

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

Теперь все, что осталось, это реализовать start_with_zeroes и end_with_zeroes. Чтобы убедиться, что блок начинается как минимум с min нулей, мы можем проверить, что он начинается с 2 ^ h нулей (где 2 ^ h ‹ = min), проверив соответствующую запись Фенвика; затем аналогичным образом проверьте, начинается ли он с 2 ^ H нулей, где 2 ^ H >= max, чтобы сократить путь в другую сторону (за исключением случаев, когда max = 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

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

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

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

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

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

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

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

• N и K - обе степени числа 2.
• N > 2K >= 4

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

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

Обратите внимание, что из-за того, что наш массив состоит из выровненных фрагментов размером 2 КБ, уровень n-k дерева будет просто состоять из количества единиц в каждом фрагменте. Однако в каждом из наших кусков одинаковое количество единиц. Это означает, что каждый узел на уровне n-k будет идентичным, что, в свою очередь, означает, что каждый узел на уровне ‹= n-k также будет идентичным.

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