Статистики на отрезках. Корневая эвристика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники)
(Запрос)
Строка 21: Строка 21:
 
Пусть мы получили запрос на нахождение суммы (минимума/максимума и т.д) на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
 
Пусть мы получили запрос на нахождение суммы (минимума/максимума и т.д) на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
  
Проверка на то, что блоки входят в отрезок полностью:
+
Таким образом, для того чтобы найти, например, сумму на отрезке <tex>[l, r]</tex> нам необходимо вручную посчитать сумму на "хвостиках" и сложить с суммой полных блоков, предпосчет которых мы сделали заранее.
* для начального блока: <tex>l ~ mod ~ len = 0</tex> ;
 
* для конечного блока: <tex>(r + 1) ~ mod ~ len = 0 </tex>.
 
  
Значит, для того чтобы найти, например, сумму на отрезке <tex>[l, r]</tex> нам необходимо вручную посчитать сумму на "хвостиках" и сложить с суммой полных блоков, предпосчет которых мы сделали заранее.
+
Пример обработки запроса "подсчет суммы на отрезке <tex>[l, r]</tex> " :
 +
<pre>
 +
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]
 +
</pre>
  
 
=== Изменение элемента ===
 
=== Изменение элемента ===

Версия 23:09, 7 мая 2012

Определение:
Корневая эвристика (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(int i = 0; i < n; i++)
    B[i / len] += A[i]

Запрос

Пусть мы получили запрос на нахождение суммы (минимума/максимума и т.д) на отрезке [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]a_i[/math], то достаточно пересчитать значение [math]b_k[/math] в том блоке, в котором этот элемент находится:

[math]b_k\ = \min(new\_value, a_j)[/math], где [math]a_j[/math] - элементы блока [math]b_k[/math]

[math](k = i / len)[/math]

Оценка сложности

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

Источники