Найти самый большой подмассив со всеми

Question

Учитывая двоичный массив (элемент 0 или 1), мне нужно найти максимальную длину подмассива, имеющего все единицы для данного диапазона (l и r) в массиве.

Мне известен подход O (n) для поиска такого подмассива, но если есть O (n) запросов, общая сложность становится O (n ^ 2).

Я знаю, что сегментное дерево используется для такого типа проблем, но я не могу понять, как построить дерево для этой проблемы.

Могу ли я построить дерево сегментов, используя которое я могу отвечать на запросы в журнале (n) так, что для O (n) запросов общая сложность станет O (nlog (n)).

Answer 1

Да, вы можете использовать дерево сегментов для решения этой проблемы.

Давайте попробуем подумать, как должно выглядеть это дерево. Очевидно, что каждый узел должен содержать длину максимального подмассива 1 с и 0 с в этом диапазоне.

Теперь, как нам объединить два узла в один больший. Другими словами, у вас есть узел, представляющий [низкий, средний) и узел, представляющий [средний, высокий). Вы должны получить максимальный подмассив для [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].

Answer 2

Пусть 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] не включительно, соответствует последовательности 1 с в A.

Теперь для любого запроса {L, R} (для диапазона [L; R] включительно) пусть S = 0. Пройдите через IL и IR с i, до 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 теперь является размером наибольшей последовательности 1 с в A между L и R.

Сложность построения IL и IR равна O(N), а сложность ответа на запрос O(M), при M длина IL или IR.