112
правок
Изменения
Добавлена часть "ответ на запрос", требуется немного дописать
<br>''Первый этап построения'':
<br> <tex> i = k </tex> : Данный каталог не имеет никаких ссылок и равен <tex> C_i </tex>.
<br> <tex> i < k </tex> : Для построения данного каталога будем сливать каталог <tex> C_i </tex> с каждым вторым элементом каталога <tex> M_{i + 1} </tex>. Каждый элемент из каталога <tex> M_{i + 1} </tex> оснастим ссылкой на позицию, откуда мы его взяли, такие ссылки будет называть ссылками вниз.
<br>''Второй этап построения'':
<br> В каждом ''модифицированном каталоге'' для каждого элемента заведем две ссылки. Для ''неподставных элементов'' это будут ссылки на минимальный ''подставной элемент'' больше текущего и на максимальный ''подставной элемент'' меньше текущего. И наоборот, если ''элемент подставной'', то ссылки будут на минимальный ''неподставной элемент'' больше текущего и на максимальный ''неподставной элемент'' больше текущего. Назовем их ссылками влево и вправо.
<br> Рассмотрим на процесс построения на примере.
=== Ответ на запрос ===
В каталоге <tex> C_1 </tex> ответ на запрос найдем с помощью бинарного поиска по <tex> С_1 </tex>. Пусть ответом для этого каталога будет ячейка <tex> cell </tex>. Далее проитерируемся по оставшимся каталогам. Для того, чтобы перейти в новый модифицированный каталог мы перейдем из <tex> cell </tex> по ссылке влево, чтобы попасть в подставную вершину, а потом из нее перейдем по ссылке вниз, чтобы попасть в следующий каталог. Если теперь <tex> cell </tex> - неподставная вершина, то нам достаточно рассмотреть двух ее соседей справа в <tex> C_i </tex>, так как <tex> cell.key < x </tex>, а каждая вторая ячейка из <tex> M_i </tex> попадает в <tex> M_{i - 1} </tex>, т.е. мы бы встретили ее ранее.
