3622
правки
Изменения
м
→Алгоритм за O(1)
У каждого элемента списка будет две метки: глобальная и локальная. Глобальная задает блок, локальная {{---}} положение элемента внутри блока. Описание взаимодействия с метками:
* <b>локальные метки</b> внутри каждого блока будут присвоены каждому элементу от <tex>0</tex> до <tex>2^{2u-1}</tex> будут жадноприсвоены. Стоит заметить, что внутри блока никогда не будет проблемы, что кому-то не хватит метки или придется сделать перераспределение меток, так как, если каждый раз в качестве метки брать среднее значение, то для того, чтобы был конфликт из-за меток, нужно больше, чем <tex>2u</tex> ключей (противоречит условию);
* <b>глобальные метки</b> будут организованы в структуру, использовавшуюся в реализации операции за логарифмическое время. Глобальные метки для блоков придется менять, когда один из блоков переполнился. Тогда блок будет разделен на два, метка второму будет присвоена методом, описанным выше (поднимемся до первого непереполненного). Каждый блок будет иметь <tex>u</tex> занятых меток. Аналогично, когда в каком-то блок становится слишком мало ключей, он будет слит с соседним.
