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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
  
'''Корневая эвристика (Sqrt-декомпозиция)''' {{---}} это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т.д.) над идущими подряд элементами некоторого множества размера <tex>n</tex> за <tex> O(\sqrt n)</tex>.
+
'''Корневая эвристика (Sqrt-декомпозиция)''' {{---}} это структура данных, которая позволяет выполнять ассоциативные операции (например, суммирование элементов, нахождение минимума/максимума и т.д.) над элементами некоторого множества за <tex> O(\sqrt n)</tex>.
  
 
== Построение ==
 
== Построение ==
Строка 12: Строка 12:
 
Пример реализации построения массива <tex>B</tex> для операции <tex> \circ </tex>:
 
Пример реализации построения массива <tex>B</tex> для операции <tex> \circ </tex>:
 
<code>
 
<code>
  '''void''' build():
+
  build()
 
     '''for''' i = 0 ... cnt
 
     '''for''' i = 0 ... cnt
 
         B[i] = neutral                <font color=green>// neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
 
         B[i] = neutral                <font color=green>// neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
Строка 34: Строка 34:
  
 
<code>
 
<code>
  '''T''' query('''int''' l, '''int''' r):
+
  query('''int''' l, '''int''' r)
 
     left = l / len
 
     left = l / len
 
     right = r / len
 
     right = r / len
 
     end = (left + 1) * len - 1
 
     end = (left + 1) * len - 1
     res = neutral                      <font color=green> // neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
+
     res = neutral                      <font color=green> //neutral {{---}} нейтральный элемент для операции <tex> \circ </tex> </font>
 
     '''if''' left == right
 
     '''if''' left == right
 
         '''for''' i = l ... r
 
         '''for''' i = l ... r
Строка 49: Строка 49:
 
         '''for''' i = right * len ... r
 
         '''for''' i = right * len ... r
 
             res = res <tex> \circ </tex> A[i]
 
             res = res <tex> \circ </tex> A[i]
 +
    '''return''' ( '''value''' res)
 
</code>
 
</code>
  
Строка 56: Строка 57:
 
== Запрос на изменение элемента ==
 
== Запрос на изменение элемента ==
 
Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.
 
Реализация данного запроса будет зависеть от того, имеет ли операция, для которой сделано построение, обратную операцию и обладает ли она свойством коммутативности.
* если оба условия выполняются, то запрос на изменение элемента можно сделать за <tex>O(1)</tex> времени,
+
* если оба условия выполняются, то запрос на изменение элемента можно сделать за <tex>O(1)</tex> времени;
 
* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.
 
* если хотя бы одно из условий не выполняется, то запрос на изменение элемента можно сделать за <tex>O(\sqrt{n})</tex> времени.
  
Строка 63: Строка 64:
 
Примеры реализации:
 
Примеры реализации:
  
* <tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить,
+
<tex>p</tex> {{---}} номер элемента из массива <tex>A</tex>, который необходимо заменить; <tex>newValue</tex> {{---}} новое значение для данного элемента.
* <tex>\mathtt{newValue}</tex> {{---}} новое значение для данного элемента.
 
  
 
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
 
Запрос на изменение элемента для операции, у которой есть обратная операция, и выполняется свойство коммутативности:
  
 
<code>
 
<code>
  '''function''' set('''int''' p, '''T''' newValue):
+
  set('''int''' p, '''value''' 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
 
     B[p / len] = tmp <tex> \circ </tex> newValue
 
     B[p / len] = tmp <tex> \circ </tex> newValue
 +
    return ('''value''' A[p])
 
</code>
 
</code>
 
'''Замечание:''' важность наличия свойства коммутативности подчеркивает следующий контрпример. Известно, что умножение матриц не коммутативно. Возьмем блок <tex> b_0 </tex>, как показано на иллюстрации выше, со следующими значениями:
 
 
<tex> b_0 = \begin{pmatrix} 27 & 32 \\ 42 & 50 \end{pmatrix} </tex> ,
 
 
<tex> a_0 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} </tex> ,
 
 
<tex> a_1 = \begin{pmatrix} 2 & 2 \\ 2 & 3 \end{pmatrix} </tex> ,
 
 
<tex> a_2 = \begin{pmatrix} 3 & 3 \\ 3 & 4 \end{pmatrix} </tex>.
 
 
Пусть необходимо изменить значение матрицы <tex> a_1 </tex> на следующее:
 
 
<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} = \begin{pmatrix} 1,5 & -1 \\ -1 & 1 \end{pmatrix} </tex>,
 
 
<tex> tmp = b \cdot a_1^{-1} = \begin{pmatrix} 8,5 & 5 \\ 13 & 8 \end{pmatrix} </tex> ,
 
 
<tex> a_1 = \begin{pmatrix} 4 & 4 \\ 4 & 5 \end{pmatrix} </tex>.
 
 
Тогда новое значение <tex> b_0  </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):
+
  set('''int''' p, '''value''' newValue)
 
     index = len * (p / len)
 
     index = len * (p / len)
 
     A[p] = newValue
 
     A[p] = newValue
Строка 114: Строка 85:
 
     '''for''' i = index ... index + len - 1
 
     '''for''' i = index ... 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]
 +
    return ('''value''' A[p])
 
</code>
 
</code>
  
Строка 121: Строка 93:
  
 
==Источники информации==
 
==Источники информации==
* [http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt-декомпозиция]
+
* [http://www.e-maxx.ru/algo/sqrt_decomposition Maximal:: algo:: Sqrt - декомпозиция]
 
* [http://habrahabr.ru/post/138946/#habracut Sqrt-декомпозиция (корневая оптимизация)]
 
* [http://habrahabr.ru/post/138946/#habracut Sqrt-декомпозиция (корневая оптимизация)]
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: