81
правка
Изменения
Нет описания правки
Теперь для каждого набора мы собираем все его поднаборы в подзадачах в один набор. Затем используя лемму два делаем разделение. Так как мы имеем неконсервативное преимущество в <tex>(h/loglogn)^g</tex> и мы работаем на уровнях не ниже чем <tex>2logloglogn</tex>, то алгоритм занимает <tex>O(qtloglogn/(g(logh - logloglogn) -logloglogn)) = O(loglogn)</tex> времени.
Мы разделили <tex>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть мы получили <tex>S_{0}</tex> < {<tex>e_{1}</tex>} < <tex>S_{1}</tex> < ... < {<tex>e_{p}</tex>} < <tex>S_{p}</tex>, где <tex>e_{i}</tex> это сегмент <tex>a_{i}</tex> полученный с помощью битового сокращения. Мы получили такое разделение комбинированием всех поднаборов в подзадачах. Предположим числа хранятся в массиве <tex>B</tex> так, что числа в <tex>S_{i}</tex> предшествуют числам в <tex>S_{j}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i - 1}</tex> но до <tex>S_{i}</tex>. Пусть <tex>B[i]</tex> в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполнится для каждого поднабора мы делаем следующее.
Помещаем все <tex>B[j]</tex> в <tex>B[j].subset</tex>
На это потребуется линейное время и место.
