Просмотр исходного текста страницы Несогласованные поддеревья. Реализация массового обновления

[[Дерево отрезков. Построение|Дерево отрезков]] позволяет осуществлять так называемые '''массовые операции''', то есть данная структура позволяет выполнять операции с несколькими подряд идущими элементами. Причем время работы, как и при других запросах, равно <tex>O(\log n)</tex>.

==Несогласованные поддеревья==
Сперва рассмотрим так называемые '''несогласованные поддеревья'''.

В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции <tex>\oplus</tex>) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок <tex>a_i..a_j</tex> хранится несогласованность <tex>d</tex>. Если в вершине хранится истинное значение суммы, то <tex>d = \perp</tex> {{---}} нейтральный элемент относительно операции <tex>\odot</tex> (например 0 для прибавления). Для реализации вторая операция должна быть ассоциативной, и операции должны удовлетворять свойству дистрибутивности:

#<tex>a \odot (b \odot c) = (a \odot b) \odot c</tex>
#<tex>(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)</tex>
#<tex>c \odot (a \oplus b) = (c \odot a) \oplus (c \odot b)</tex>

==Массовое обновление==

Рассмотрим в общем виде реализацию массовой операции на отрезке. Пусть необходимо отвечать запросы относительно операции <tex>\oplus</tex>, а запрос массового обновления идет по операции <tex>\odot</tex>.

Для эффективной реализаций будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно результата выполнения операции <tex>\oplus</tex>, храним несогласованность {{---}} величина, с которой нужно выполнить операцию <tex>\odot</tex> для всех элементов текущего отрезка. Тем самым мы сможем обрабатывать запрос массового обновления на любом подотрезке эффективно, вместо того чтобы изменять все <tex>O(N)</tex> значений. Как известно из определения несогласованных поддеревьев, в текущий момент времени не в каждой вершине дерева хранится истинное значение, однако когда мы обращаемся к текущему элементу мы работаем с верными данными. Это обеспечивается так называемым "проталкиванием" несогласованности детям (процедура push) при каждом обращений к текущей вершине. При этом после обращения к вершине необходимо пересчитать значение по операции <tex>\oplus</tex>, так как значение в детях могло измениться.

А ответ же на запрос по операции <tex>\oplus</tex> реализуется почти так же, как и в случае без массовых обновлений. Отличие лишь в том, что следует во-первых не забыть раздать детям несогласованность, и во-вторых пересчитать свое значение. 

Таким образом в обоих запросах очень важно протолкнуть детям несогласованность, вызвать функцию от детей и, наконец, пересчитать значение в текущей вершине.

==Псевдокод в общем виде==
Пусть поступают запросы двух типов {{---}} поиск элемента, соответствующего операции <tex>\oplus</tex>, и массовое обновление на отрезке относительно операции <tex>\odot</tex>. Используется классическая реализация дерева отрезка с полуинтервалами.
 
Пусть в узлах дерева хранятся структуры из четырех полей:
* <tex>left</tex> {{---}} левая граница полуинтервала, за который "отвечает" текущая вершина.
* <tex>right</tex> {{---}} правая граница этого полуинтервала.
* <tex> ans</tex> {{---}} сумма на отрезке по операции <tex>\oplus</tex>.
* <tex> d</tex> {{---}} несогласованность.

    // Процедура "проталкивания" несогласованности детям
 void push(int node) {
        tree[2 * node + 1].d = tree[2 * node + 1].d <tex>\odot</tex> tree[node].d;
        tree[2 * node + 2].d = tree[2 * node + 2].d <tex>\odot</tex> tree[node].d;
        tree[node].d = <tex>\perp</tex>; // Нейтральный элемент
 } 
    // Процедура ответа на множественные запросы.  
 void update(int node, int a, int b, my_type val) {
    // val - значение, которое поступило в качестве параметра на запрос
        l = tree[node].left;
        r = tree[node].right; 
        '''if'''  [l, r) <tex>\bigcap </tex> [a, b) == <tex> \varnothing</tex>
            return;
        '''if''' [l, r) <tex>\subset </tex> [a, b)
            tree[node].d = tree[node].d <tex>\odot</tex> val;
            return;
 
        push(node); 
    // Вызываем обновление детей
        update(2 * node + 1, a, b, val);
        update(2 * node + 2, a, b, val);
     // Пересчитываем свое значение
        tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex> 
                          (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d);
 }
    // Функция ответа на запросы
 my_type get_ans(int node, int a, int b) {
    // node - текущая вершина, a и b - границы запроса
        l = tree[node].left;
        r = tree[node].right; 
        '''if'''  [l, r )<tex>\bigcap </tex> [a, b) == <tex> \varnothing</tex>
            return <tex>\perp</tex>;
        '''if''' [l, r)  <tex>\subset </tex> [a, b)
            return tree[node].ans <tex>\odot</tex> tree[node].d;
        push(node);   
        int ans = get_ans (node * 2 + 1, a, b) <tex>\oplus</tex>  
                 get_ans (node * 2 + 2, a, b));
        tree[node].ans = (tree[2 * node + 1].ans <tex>\odot</tex> tree[2 * node + 1].d) <tex>\oplus</tex> 
                          (tree[2 * node + 2].ans <tex>\odot</tex> tree[2 * node + 2].d);
        return ans;
 }

==Ссылки==

[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]

[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BE%D1%82%D1%80%D0%B5%D0%B7%D0%BA%D0%BE%D0%B2  Дерево отрезков — Википедия]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Дерево отрезков]]