Изменения

В каталоге <tex> C_1 </tex> ответ на запрос найдем с помощью бинарного поиска по <tex> С_1 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>, т.е. мы бы встретили ее ранее.