<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
		<id>https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=178.178.10.103&amp;*</id>
		<title>Викиконспекты - Вклад участника [ru]</title>
		<link rel="self" type="application/atom+xml" href="https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=178.178.10.103&amp;*"/>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/178.178.10.103"/>
		<updated>2026-11-18T23:43:07Z</updated>
		<subtitle>Вклад участника</subtitle>
		<generator>MediaWiki 1.30.0</generator>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%81%D0%BE%D0%B3%D0%BB%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D0%B4%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F._%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D0%BD%D0%BE%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&amp;diff=22836</id>
		<title>Несогласованные поддеревья. Реализация массового обновления</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%9D%D0%B5%D1%81%D0%BE%D0%B3%D0%BB%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D0%B4%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D1%8C%D1%8F._%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%BC%D0%B0%D1%81%D1%81%D0%BE%D0%B2%D0%BE%D0%B3%D0%BE_%D0%BE%D0%B1%D0%BD%D0%BE%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&amp;diff=22836"/>
				<updated>2012-05-28T18:45:29Z</updated>
		
		<summary type="html">&lt;p&gt;178.178.10.103: /* Псевдокод */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;Дерево отрезков позволяет отвечать на запросы к целым отрезкам подряд идущих элементов, причем за то же время  &amp;lt;tex&amp;gt;O(\log n)&amp;lt;/tex&amp;gt;.&lt;br /&gt;
==Несогласованные поддеревья==&lt;br /&gt;
Сперва рассмотрим так называемые '''несогласованные поддеревья'''.&lt;br /&gt;
&lt;br /&gt;
В несогласованном поддереве дерева отрезков в вершинах хранятся не истинные значения сумм (по операции &amp;lt;tex&amp;gt;\oplus&amp;lt;/tex&amp;gt;) на отрезках, однако гарантируется, что на запрос они отвечают верно. При этом в корне поддерева, которому соответствует отрезок &amp;lt;tex&amp;gt;a_i..a_j&amp;lt;/tex&amp;gt; хранится несогласованность &amp;lt;tex&amp;gt;d&amp;lt;/tex&amp;gt;. Если в вершине хранится истинное значение суммы, то &amp;lt;tex&amp;gt;d = \perp&amp;lt;/tex&amp;gt; {{---}} нейтральный элемент относительно операции &amp;lt;tex&amp;gt;\odot&amp;lt;/tex&amp;gt; (например 0 для прибавления). Для реализации вторая операция должна быть ассоциативной, и операций должны удовлетворять свойству дистрибутивность:&lt;br /&gt;
&lt;br /&gt;
#&amp;lt;tex&amp;gt;a \odot (b \odot c) = (a \odot b) \odot c&amp;lt;/tex&amp;gt;&lt;br /&gt;
#&amp;lt;tex&amp;gt;(a \oplus b) \odot c = (a \odot c) \oplus (b \odot c)&amp;lt;/tex&amp;gt;&lt;br /&gt;
#&amp;lt;tex&amp;gt;c \odot (a \oplus b) = (c \odot a) \oplus (c \odot b)&amp;lt;/tex&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Если операция &amp;lt;tex&amp;gt;\odot&amp;lt;/tex&amp;gt; не коммутативна, то при запросах нужно, во-первых, раздать детям несогласованность, во-вторых, вызвать функцию от детей и, в-третьих, пересчитать свое значение. Очень важно выполнить все три пункта. &lt;br /&gt;
==Массовое обновление==&lt;br /&gt;
&lt;br /&gt;
==Пример==&lt;br /&gt;
&lt;br /&gt;
Рассмотрим массовые операции на отрезке на примере задачи &amp;quot;Прибавление на отрезке&amp;quot;. При этом мы должны отвечать на запрос минимума на отрезке.&lt;br /&gt;
&lt;br /&gt;
Для эффективной реализаций будем использовать описанную выше структуру {{---}} несогласованные поддеревья. В каждой вершине, помимо непосредственно суммы, храним несогласованность {{---}} сколько необходимо прибавить ко всем числам этого отрезка(соответственно при запросе минимума истинный минимум на отрезке при корректной несогласованности {{---}} сумма несогласованности и значения в вершине). Тем самым мы сможем обрабатывать запрос прибавления на любом подотрезке эффективно, вместо того чтобы изменять все &amp;lt;tex&amp;gt;O(N)&amp;lt;/tex&amp;gt;значений.&lt;br /&gt;
&lt;br /&gt;
Если теперь приходит запрос минимального значения на отрезке, то нам достаточно спуститься по дереву, &amp;quot;протолкнув&amp;quot; все встреченные по пути несогласованности, записанные в вершинах дерева.&lt;br /&gt;
&lt;br /&gt;
==Псевдокод==&lt;br /&gt;
Используется классическая реализация дерева отрезка с полуинтервалами.&lt;br /&gt;
&lt;br /&gt;
Пусть в узлах дерева хранятся структуры из четырех полей:&lt;br /&gt;
* &amp;lt;tex&amp;gt;left&amp;lt;/tex&amp;gt; {{---}} левая граница полуинтервала, за который &amp;quot;отвечает&amp;quot; текущая вершина.&lt;br /&gt;
* &amp;lt;tex&amp;gt;right&amp;lt;/tex&amp;gt; {{---}} правая граница этого полуинтервала.&lt;br /&gt;
* &amp;lt;tex&amp;gt; min&amp;lt;/tex&amp;gt; {{---}} минимум на полуинтервале.&lt;br /&gt;
* &amp;lt;tex&amp;gt; d&amp;lt;/tex&amp;gt; {{---}} несогласованность.&lt;br /&gt;
&lt;br /&gt;
    // Процедура &amp;quot;проталкивания&amp;quot; несогласованности детям&lt;br /&gt;
 void push(int node) {&lt;br /&gt;
        tree[2 * node + 1].d += tree[node].d;&lt;br /&gt;
        tree[2 * node + 2].d += tree[node].d;&lt;br /&gt;
        tree[node].d = 0;&lt;br /&gt;
 } &lt;br /&gt;
 &lt;br /&gt;
 int get_min(int node, int a, int b) {&lt;br /&gt;
    // node - текущая вершина, a и b - границы запроса&lt;br /&gt;
        l = tree[node].left;&lt;br /&gt;
        r = tree[node].right; &lt;br /&gt;
        if  [l, r)&amp;lt;tex&amp;gt;\bigcap &amp;lt;/tex&amp;gt;[a, b) == &amp;lt;tex&amp;gt; \varnothing&amp;lt;/tex&amp;gt;&lt;br /&gt;
            return &amp;lt;tex&amp;gt;\infty&amp;lt;/tex&amp;gt;;&lt;br /&gt;
        if [l, r) == [a, b)&lt;br /&gt;
            return tree[node].min + tree[node].d;&lt;br /&gt;
        push(node);   &lt;br /&gt;
        int m = (l + r) / 2;&lt;br /&gt;
        int ans = min(get_min (node * 2 + 1, a, min(b, m)), &lt;br /&gt;
                 get_min (node * 2 + 2, max(a, m), b)));&lt;br /&gt;
        tree[node].min = ans;&lt;br /&gt;
     // Пересчитываем свое значение&lt;br /&gt;
        tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d, &lt;br /&gt;
                          tree[2 * node + 2].min + tree[2 * node + 2].d); &lt;br /&gt;
 }&lt;br /&gt;
  &lt;br /&gt;
 void update(int node, int a, int b, int val) {&lt;br /&gt;
    // val - значение, на которое нужно увеличить отрезок&lt;br /&gt;
        l = tree[node].left;&lt;br /&gt;
        r = tree[node].right; &lt;br /&gt;
        if  [l, r)&amp;lt;tex&amp;gt;\bigcap &amp;lt;/tex&amp;gt;[a, b) == &amp;lt;tex&amp;gt; \varnothing&amp;lt;/tex&amp;gt;&lt;br /&gt;
            return;&lt;br /&gt;
        if [l, r) == [a, b)&lt;br /&gt;
            tree[node].d += val;&lt;br /&gt;
            return;&lt;br /&gt;
 &lt;br /&gt;
        push(node); &lt;br /&gt;
    // Вызываем обновление детей&lt;br /&gt;
        update(2 * node + 1, a, b, val);&lt;br /&gt;
        update(2 * node + 2, a, b, val);&lt;br /&gt;
        tree[node].min = min(tree[2 * node + 1].min + tree[2 * node + 1].d, &lt;br /&gt;
                          tree[2 * node + 2].min + tree[2 * node + 2].d);&lt;br /&gt;
 }&lt;br /&gt;
&lt;br /&gt;
==Ссылки==&lt;br /&gt;
&lt;br /&gt;
[http://e-maxx.ru/algo/segment_tree MAXimal :: algo :: Дерево отрезков]&lt;br /&gt;
&lt;br /&gt;
[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  Дерево отрезков — Википедия]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Дискретная математика и алгоритмы]]&lt;br /&gt;
[[Категория: Дерево отрезков]]&lt;/div&gt;</summary>
		<author><name>178.178.10.103</name></author>	</entry>

	</feed>