Статистики на отрезках. Корневая эвристика

Материал из Викиконспекты
Версия от 18:31, 16 мая 2012; Whiplash (обсуждение | вклад) (→‎Запрос на изменение элемента)
Перейти к: навигация, поиск
Определение:
Корневая эвристика (Sqrt-декомпозиция) — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за [math] O(\sqrt n)[/math].


Предпосчет

Sqrt.png

Пусть нам дан массив [math]A[/math] размерности [math]n[/math]. Cделаем следующий предпосчет:

  • разделим массив [math]A[/math] на блоки длины [math]len = \lfloor \sqrt{n} \rfloor[/math] ;
  • в каждом блоке заранее предпосчитаем необходимую нам операцию;
  • результаты предпосчёта запишем в массив [math]B[/math] размерности [math]cnt[/math], где [math]cnt = \left\lceil \frac{n}{len} \right\rceil[/math] — количество блоков.


Пример реализации предпосчета для запроса "подсчет суммы": 

for i = 0 to n - 1
    B[i / len] += A[i]


Пердпосчет, очевидно, происходит за [math]O(n)[/math] времени.

Обработка запроса

Sqrt(sum).png

Пусть мы получили запрос на выполнение операции на отрезке [math][l, r][/math]. Отрезок может охватить некоторые блоки массива [math]B[/math] полностью, а так же не более двух блоков (начальный и конечный) - не полностью.

Таким образом, для того чтобы найти результат операции на отрезке [math][l, r][/math] нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, предпосчет которых мы сделали заранее.


Пример реализации обработки запроса "подсчет суммы на отрезке [math][l, r][/math] " : 

left = l / len
right = r / len
end = (left + 1) * len - 1
sum = 0

if left == right
    for i = l to r
	sum += A[i]
else
    for i = l to end
        sum += A[i]
    for i = left + 1 to right - 1
        sum += B[i]
    for i = right * len to r
        sum += A[i]


Размер каждого из "хвостов", очевидно, не превосходит длины блока [math]len[/math], а количество блоков не превосходит [math]cnt[/math]. Поскольку и [math]len[/math], и [math]cnt[/math] мы выбирали [math]~ ~ \approx \sqrt{n}[/math], то для выполнения операции на отрезке [math][l, r][/math] нам понадобится [math]O(\sqrt{n})[/math] времени.

Запрос на изменение элемента

Sqrt(+delta).png

Реализации данного запроса будет зависеть от того, имеет ли операция, для которой мы сделали предпосчет, обратную операцию и обладает ли она свойством коммутативности.

  • если обратная операция существует, и выполняется свойство коммутативности, то нам не придется заново пересчитывать значение для блока, достаточно будет поменять всего два элемента;
  • если хотя бы одно из условий не выполняется, то нам придется заново пересчитать значение для блока, к которому принадлежит элемент указанный в запросе, и записать полученный результат в соответствующий элемент массива [math]B[/math].


Примеры реализации:

[math]p[/math] - номер элемента из массива [math]A[/math], который необходимо заменить; [math]newValue[/math] - новое значение для данного элемента.

Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности: 

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

Запрос на изменение элемента для поиска минимума (выполняется свойство коммутативности, но нет обратной операции): 

index = len * (p / cnt)
A[p] = newValue
for i = index to index + len - 1
    B[p / len] = min(A[i], A[i + 1])


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

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Статистики_на_отрезках._Корневая_эвристика&oldid=22413»