3622
правки
Изменения
м
А должно получиться Хотя правильный результат: <tex> b_0 = \begin{pmatrix} 51 & 60 \\ 78 & 92 \end{pmatrix} </tex>. Противоречие. Значит, коммутативность важна.
→Запрос на изменение элемента
right = r / len
end = (left + 1) * len - 1
res = neutral <font color=green> //neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
'''if''' left == right
'''for''' i = l ... r
== Запрос на изменение элемента ==
Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.
* если оба условия выполняются, то запрос на изменение элемента можно сделать за <tex>O(1)</tex> времени;,
* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.
Примеры реализации:
* <tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить; , * <tex>\mathtt{newValue}</tex> {{---}} новое значение для данного элемента.
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
<code>
'''Tfunction''' set('''int''' p, '''valueT''' newValue):
tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) <font color=green>// inverse(A[p]) {{---}} обратный элемент</font>
A[p] = newValue
Пусть необходимо изменить значение матрицы <tex> a_1 </tex> на следующее:
<tex> \mathtt{newValue} = </tex> <tex> new </tex> <tex> a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} </tex>.
Тогда значения <tex> a_1^{-1} </tex>, <tex> tmp </tex> и новое значение <tex> a_1 </tex> таковы :
<tex> b_0 = \begin{pmatrix} 54 & 59 \\ 84 & 92 \end{pmatrix} </tex>.
Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется:
<code>
'''Tfunction''' set('''int''' p, '''valueT''' newValue):
index = len * (p / len)
A[p] = newValue
