Изменения

change(p, newValue) tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) // <tex> \circ </tex> - операция, для которой был сделан предпосчет; inverse(A[p]) - обратный элемент A[p] = newValue B[p / len] = tmp <tex> \circ </tex> newValue

Запрос на изменение элемента для поиска минимума (операции, у которой хотя бы одно из условий не выполняется свойство коммутативности, но нет обратной операции): <pre>index = len * p / cntA[p] = newValueB[p / len] = newValuefor i = index to index + len B[p / len] = min(A[i], B[p / len])</pre>

Таким образомЗапрос на изменение элемента в первом случае происходит за <tex>O(1)</tex> времени, запрос на во втором случае изменение элемента происходит не более чем за длину блока <tex>len</tex>, т.е. не более чем за <tex>O(\sqrt{n})</tex> времени.