Изменения

<br>''Первый этап построения'':

<br>''Второй этап построения'':<br> * В каждом ''модифицированном каталоге'' для каждого элемента заведем две ссылки. Для ''неподставных элементов'' это будут ссылки на максимальный''подставной элемент'' меньше текущего и на минимальный любого типа больше текущего. Если ''элемент подставной'', то ссылки будут на минимальный ''неподставной элемент" больше текущего и на максимальный ''неподставной элемент'' меньше текущего. Назовем их ссылками влево и вправо.

*В первом каталоге ответ на запрос найдем с помощью бинарного поиска по <tex> C_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>, т.е. мы бы встретили ее ранее и перешли мы вниз по ней, но это этого не случилось. **Обновив cell максимальным из подходящих значений нужно проверить, является ли она ''подставным элементом'', если да, то перейдем по ссылке влево, попав в ответ для текущего каталога, иначе это и будет ответ.