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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение)
(Обработка запроса)
Строка 25: Строка 25:
 
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{---}} не полностью.
 
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) {{---}} не полностью.
  
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
+
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
  
 
[[Файл:sqrt(sum).png|358px]]
 
[[Файл:sqrt(sum).png|358px]]
Строка 52: Строка 52:
  
  
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>~ ~ \approx \sqrt{n}</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> нам понадобится <tex>O(\sqrt{n})</tex> времени.
+
Размер каждого из "хвостов", очевидно, не превосходит длины блока <tex>len</tex>, а количество блоков не превосходит <tex>cnt</tex>. Поскольку и <tex>len</tex>, и <tex>cnt</tex> мы выбирали <tex>~ ~ \approx \sqrt{n}</tex>, то для выполнения операции на отрезке <tex>[l, r]</tex> понадобится <tex>O(\sqrt{n})</tex> времени.
  
 
== Запрос на изменение элемента ==
 
== Запрос на изменение элемента ==

Версия 19:42, 8 мая 2015

Корневая эвристика (Sqrt-декомпозиция) — это метод, или структура данных, которая позволяет выполнять ассоциативные операции над отрезками (например, суммирование элементов, нахождение минимума/максимума и т.д.) за [math] O(\sqrt n)[/math].

Построение

Пусть нам дан массив [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 \dfrac{n}{len} \right\rceil[/math] — количество блоков.

Sqrt.png

Пример реализации построения массива [math]B[/math] для операции [math] \circ [/math]:

build()
    for i = 0 ... cnt
        B[i] = neutral                // neutral - нейтральный элемент для операции [math] \circ [/math] 
    for i = 0 ... n - 1
        B[i / len] = B[i / len] [math] \circ [/math] A[i]


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

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

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

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

Sqrt(sum).png

Пример реализации обработки запроса:

[math] \circ [/math] — операция, для которой было сделано построение.

query(l, r)
    left = l / len
    right = r / len
    end = (left + 1) * len - 1
    res = neutral                       //neutral - нейтральный элемент для операции [math] \circ [/math] 
    if left == right
        for i = l ... r
            res = res [math] \circ [/math] A[i]
    else
        for i = l ... end
            res = res [math] \circ [/math] A[i]
        for i = left + 1 ... right - 1
            res = res [math] \circ [/math] B[i]
        for i = right * len ... r
            res = res [math] \circ [/math] 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] времени.

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

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

  • если оба условия выполняются, то запрос на изменение элемента мы можем сделать за [math]O(1)[/math] времени;
  • если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за [math]O(\sqrt{n})[/math] времени.

Sqrt(+delta).png

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

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

[math] \circ [/math] — операция, для которой было сделано построение.

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

set(p, newValue)
    tmp = B[p / len] [math] \circ [/math] inverse(A[p])   // inverse(A[p]) - обратный элемент
    A[p] = newValue
    B[p / len] = tmp [math] \circ [/math] newValue

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

set(p, newValue)
    index = len * (p / len)
    A[p] = newValue
    B[p / len] = neutral              // neutral - нейтральный элемент для операции [math] \circ [/math] 
    for i = index ... index + len - 1
        B[p / len] = B[p / len] [math] \circ [/math] A[i]

Источники информации