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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Обработка запроса)
Строка 3: Строка 3:
 
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>. }}
 
'''Корневая эвристика (Sqrt-декомпозиция)''' — это метод, или структура данных, которая позволяет выполнять некоторые ассоциативные операции над отрезками (суммирование элементов подмассива, нахождение минимума/максимума и т.д.) за <tex> O(\sqrt n)</tex>. }}
  
== Предпосчет ==
+
== Построение ==
 
[[Файл:sqrt.png|right|540px]]
 
[[Файл:sqrt.png|right|540px]]
Пусть нам дан массив <tex>A</tex> размерности <tex>n</tex>. Cделаем следующий предпосчет:
+
Пусть нам дан массив <tex>A</tex> размерности <tex>n</tex>. Cделаем следующие действия:
 
* разделим массив <tex>A</tex> на блоки длины <tex>len = \lfloor \sqrt{n} \rfloor</tex> ;  
 
* разделим массив <tex>A</tex> на блоки длины <tex>len = \lfloor \sqrt{n} \rfloor</tex> ;  
* в каждом блоке заранее предпосчитаем необходимую нам операцию;
+
* в каждом блоке заранее посчитаем необходимую нам операцию;
* результаты предпосчёта запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков.
+
* результаты подсчета запишем в массив <tex>B</tex> размерности <tex>cnt</tex>, где <tex>cnt = \left\lceil \frac{n}{len} \right\rceil</tex> — количество блоков.
  
  
Пример реализации предпосчета для операции <tex> \circ </tex>:
+
Пример реализации построения массива <tex>B</tex> для операции <tex> \circ </tex>:
 
<code>
 
<code>
  precalc()
+
  build()
 +
    for i = 0 to cnt
 +
        B[i] = ???  // где ??? - нейтральный элемент для операции <tex> \circ </tex>
 
     for i = 0 to n - 1
 
     for i = 0 to n - 1
         if i % len == 0
+
         B[i / len] = B[i / len] <tex> \circ </tex> A[i]
            B[i / len] = A[i]
 
        else
 
            B[i / len] = B[i / len] <tex> \circ </tex> A[i]
 
 
</code>
 
</code>
  
  
Пердпосчет, очевидно, происходит за <tex>O(n)</tex> времени.
+
Построение, очевидно, происходит за <tex>O(n)</tex> времени.
  
 
== Обработка запроса ==
 
== Обработка запроса ==
Строка 28: Строка 27:
 
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
 
Пусть мы получили запрос на выполнение операции на отрезке <tex>[l, r]</tex>. Отрезок может охватить некоторые блоки массива <tex>B</tex> полностью, а так же не более двух блоков (начальный и конечный) - не полностью.
  
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, предпосчет которых мы сделали заранее.
+
Таким образом, для того чтобы найти результат операции на отрезке <tex>[l, r]</tex> нам необходимо вручную выполнить ее на "хвостах", а потом выполнить ее для полученного результата и полных блоков, значения которых мы посчитали заранее.
  
  
 
Пример реализации обработки запроса:
 
Пример реализации обработки запроса:
  
<tex> \circ </tex> - операция, для которой был сделан предпосчет.
+
<tex> \circ </tex> - операция, для которой было сделано построение.
  
 
<code>
 
<code>
Строка 40: Строка 39:
 
     right = r / len
 
     right = r / len
 
     end = (left + 1) * len - 1
 
     end = (left + 1) * len - 1
     res = a[l]
+
     res = ???  // где ??? - нейтральный элемент для операции <tex> \circ </tex>
 
     if left == right
 
     if left == right
         for i = l + 1 to r
+
         for i = l to r
 
      res = res <tex> \circ </tex> A[i]
 
      res = res <tex> \circ </tex> A[i]
 
     else
 
     else
         for i = l + 1 to end
+
         for i = l to end
 
             res = res <tex> \circ </tex> A[i]
 
             res = res <tex> \circ </tex> A[i]
 
         for i = left + 1 to right - 1
 
         for i = left + 1 to right - 1
Строка 58: Строка 57:
 
== Запрос на изменение элемента ==
 
== Запрос на изменение элемента ==
 
[[Файл:sqrt(+delta).png|right|264px]]
 
[[Файл:sqrt(+delta).png|right|264px]]
Реализации данного запроса будет зависеть от того, имеет ли операция, для которой мы сделали предпосчет, обратную операцию и обладает ли она свойством коммутативности.
+
Реализации данного запроса будет зависеть от того, имеет ли операция, для которой мы сделали построение, обратную операцию и обладает ли она свойством коммутативности.
* если обратная операция существует, и выполняется свойство коммутативности, то нам не придется заново пересчитывать значение для блока;
+
* если оба условия выполняются, то запрос на изменение элемента мы можем сделать за <tex>O(1)</tex> времени;
* если хотя бы одно из условий не выполняется, то нам придется заново пересчитать значение для блока, к которому принадлежит элемент указанный в запросе, и записать полученный результат в соответствующий элемент массива <tex>B</tex>.
+
* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.
  
  
Строка 67: Строка 66:
 
<tex>p</tex> - номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>newValue</tex> - новое значение для данного элемента.
 
<tex>p</tex> - номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>newValue</tex> - новое значение для данного элемента.
  
<tex> \circ </tex> - операция, для которой был сделан предпосчет.
+
<tex> \circ </tex> - операция, для которой было сделано построение.
  
 
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
 
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
  
 
<code>
 
<code>
  change(p, newValue)
+
  set(p, newValue)
 
     tmp = B[p / len] <tex> \circ </tex> inverse(A[p])  // inverse(A[p]) - обратный элемент
 
     tmp = B[p / len] <tex> \circ </tex> inverse(A[p])  // inverse(A[p]) - обратный элемент
 
     A[p] = newValue
 
     A[p] = newValue
Строка 81: Строка 80:
  
 
<code>
 
<code>
  change(p, newValue)
+
  set(p, newValue)
 
     index = len * (p / len)
 
     index = len * (p / len)
 
     A[p] = newValue
 
     A[p] = newValue
     B[p / len] = A[index]
+
     B[p / len] = ???  // где ??? - нейтральный элемент для операции <tex> \circ </tex>
     for i = index + 1 to index + len - 1
+
     for i = index to index + len - 1
 
         B[p / len] = B[p / len] <tex> \circ </tex> A[i]
 
         B[p / len] = B[p / len] <tex> \circ </tex> A[i]
 
</code>
 
</code>
 
 
Запрос на изменение элемента в первом случае происходит за <tex>O(1)</tex> времени, во втором случае изменение элемента происходит за длину блока <tex>len</tex>, т.е. за <tex>O(\sqrt{n})</tex> времени.
 
  
 
==Источники==
 
==Источники==

Версия 18:11, 25 мая 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] — количество блоков.


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

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


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

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

Sqrt(sum).png

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

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


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

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

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

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

Sqrt(+delta).png

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

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


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

[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] = ???   // где ??? - нейтральный элемент для операции [math] \circ [/math]
    for i = index to index + len - 1
        B[p / len] = B[p / len] [math] \circ [/math] A[i]

Источники