Статистики на отрезках. Корневая эвристика — различия между версиями
Shersh (обсуждение | вклад) м (→Запрос на изменение элемента) |
м (rollbackEdits.php mass rollback) |
||
(не показано 6 промежуточных версий 2 участников) | |||
Строка 63: | Строка 63: | ||
Примеры реализации: | Примеры реализации: | ||
− | <tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить | + | * <tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить, |
+ | * <tex>\mathtt{newValue}</tex> {{---}} новое значение для данного элемента. | ||
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности: | Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности: | ||
<code> | <code> | ||
− | ''' | + | '''function''' set('''int''' p, '''T''' newValue): |
tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) <font color=green>// inverse(A[p]) {{---}} обратный элемент</font> | tmp = B[p / len] <tex> \circ </tex> inverse(A[p]) <font color=green>// inverse(A[p]) {{---}} обратный элемент</font> | ||
A[p] = newValue | A[p] = newValue | ||
Строка 86: | Строка 87: | ||
Пусть необходимо изменить значение матрицы <tex> a_1 </tex> на следующее: | Пусть необходимо изменить значение матрицы <tex> a_1 </tex> на следующее: | ||
− | <tex> newValue= | + | <tex> \mathtt{newValue} = a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} </tex>. |
Тогда значения <tex> a_1^{-1} </tex>, <tex> tmp </tex> и новое значение <tex> a_1 </tex> таковы : | Тогда значения <tex> a_1^{-1} </tex>, <tex> tmp </tex> и новое значение <tex> a_1 </tex> таковы : | ||
Строка 102: | Строка 103: | ||
<tex> b_0 = \begin{pmatrix} 54 & 59 \\ 84 & 92 \end{pmatrix} </tex>. | <tex> b_0 = \begin{pmatrix} 54 & 59 \\ 84 & 92 \end{pmatrix} </tex>. | ||
− | + | Хотя правильный результат: <tex> b_0 = \begin{pmatrix} 51 & 60 \\ 78 & 92 \end{pmatrix} </tex>. | |
Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется: | Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется: | ||
<code> | <code> | ||
− | ''' | + | '''function''' set('''int''' p, '''T''' newValue): |
index = len * (p / len) | index = len * (p / len) | ||
A[p] = newValue | A[p] = newValue |
Текущая версия на 19:30, 4 сентября 2022
Корневая эвристика (Sqrt-декомпозиция) — это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера
за .Построение
Пусть дан массив
размерности . Cделаем следующие действия:- разделим массив на блоки длины ,
- в каждом блоке заранее посчитаем необходимую операцию,
- результаты подсчета запишем в массив размерности , где — количество блоков.
Пример реализации построения массива
void build(): for i = 0 ... cnt B[i] = neutral // neutral — нейтральный элемент для операцииfor i = 0 ... n - 1 B[i / len] = B[i / len] A[i]
Построение, очевидно, происходит за времени.
Обработка запроса
Пусть получен запрос на выполнение операции на отрезке
. Отрезок может охватить некоторые блоки массива полностью, а так же не более двух блоков (начальный и конечный) — не полностью.Таким образом, для того чтобы найти результат операции на отрезке
необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.Пример реализации обработки запроса:
— операция, для которой было сделано построение.
T query(int l, int r): left = l / len right = r / len end = (left + 1) * len - 1 res = neutral // neutral — нейтральный элемент для операцииif left == right for i = l ... r res = res A[i] else for i = l ... end res = res A[i] for i = left + 1 ... right - 1 res = res B[i] for i = right * len ... r res = res A[i]
Размер каждого из "хвостов", очевидно, не превосходит длины блока , а количество блоков не превосходит . Поскольку было выбрано равным , а было выбрано равным , то для выполнения операции на отрезке понадобится времени.
Запрос на изменение элемента
Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.
- если оба условия выполняются, то запрос на изменение элемента можно сделать за времени,
- если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за времени.
Примеры реализации:
- — номер элемента из массива , который необходимо заменить,
- — новое значение для данного элемента.
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
function set(int p, T newValue): tmp = B[p / len]inverse(A[p]) // inverse(A[p]) — обратный элемент A[p] = newValue B[p / len] = tmp newValue
Замечание: важность наличия свойства коммутативности подчеркивает следующий контрпример. Известно, что умножение матриц не коммутативно. Возьмем блок
, как показано на иллюстрации выше, со следующими значениями:,
,
,
.
Пусть необходимо изменить значение матрицы
на следующее:.
Тогда значения
, и новое значение таковы :
,
,
.
Тогда новое значение
следующее:
.
Хотя правильный результат:
.Запрос на изменение элемента для операции, у которой хотя бы одно из условий не выполняется:
function set(int p, T newValue): index = len * (p / len) A[p] = newValue B[p / len] = neutral // neutral — нейтральный элемент для операцииfor i = index ... index + len - 1 B[p / len] = B[p / len] A[i]