Public ATP Wiki - Вклад участника [ru]

АВЛ-дерево

2020-05-25T00:44:13Z

Algocourselecturenotes: Новая страница: «==АВЛ-дерево== ===Определение и свойства=== '''АВЛ-дерево''' - сбалансированное по высоте двоич…»

==АВЛ-дерево==
===Определение и свойства===
'''АВЛ-дерево''' - сбалансированное по высоте двоичное дерево поиска, высоты поддеревьев каждого узла которого различаются не более, чем на 1.

Аббревиатура АВЛ происходит от первых букв фамилий создателей АВЛ-дерева советских учёных Георгия Максимовича Адельсон-Вельского и Евгения Михайловича Ландиса.

==Высота дерева==
===Лемма о высоте===

Пусть mh - минимальное число вершин в АВЛ-дереве высотой h, тогда mh = Fh+2 - 1, где Fh - h-ое число Фибоначчи.

===Доказательство леммы===

Из свойств АВЛ-дерева следует, что mh+2 = mh + mh+1 + 1 (два поддерева высотами h и h+1 и их вершина-родитель).

Докажем по индукции равенство mh = Fh+2 - 1.

База индукции: m1 = F3 - 1 верно, т.к. m1 = 1, F3 = 2.

Тогда имеем mh+1 = mh + mh-1 + 1 = Fh+2 - 1 + Fh+1 - 1 + 1 = Fh+3 - 1.

Таким образом, равенство mh = Fh+2 - 1 доказано.

===Высота дерева===

Fh = Ω(φh), φ=(√5+1)/2.

То есть n ⩾ φh.

Прологарифмировав обе части, получим:

logφn ⩾ h

Таким образом, высота АВЛ-дерева - O(log n).

==Балансировка==
Для поддержания сбалансированности дерева будем в каждой вершине хранить разность высот её поддеревьев diff[i].

'''Балансировка вершины''' - операция, которая в случае, если разность высот правого и левого поддеревьев АВЛ-дерева равна 2, изменяет связи "предок-потомок" в поддеревьях данной вершины так, что разность вершин в данном дереве составляет по модулю ⩽ 1. Операция осуществляется посредством вращения поддерева данной вершины.

Наивное дерево поиска

2020-05-24T21:58:40Z

Algocourselecturenotes: /* Удаление */

==Определение и свойства==
'''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура данных двоичное дерево, для любого узла которого выполняются следующие свойства:
# Оба узла поддерева являются двоичными деревьями поиска;
# Все значения ключей левого поддерева меньше ключа узла;
# Все значения ключей правого поддерева больше ключа узла.
[[Файл:BST.png|200 px|right|thumb|Двоичное дерево поиска]]
==Операции над деревом==
===Поиск===
====Алгоритм====
Поиск узла по заданному ключу можно осуществлять рекурсивно, начиная из вершины.
# Если узел отсутствует, возвращаем нулевой указатель.
# Если значение в узле равно ключу, возвращаем указатель на узел.
# Если значение в узле больше ключа, запускаем поиск по ключу в левом поддереве.
# Если значение в узле меньше ключа, запускаем поиск по ключу в правом поддереве.
====Реализация на языке C====
node_t* find (node_t* head, elem_t key) { 
&emsp;'''if''' (!head) 
&emsp;&emsp;'''return''' ''NULL''; 
&emsp;if (head->data == key) 
&emsp;&emsp;'''return''' head; 
&emsp;'''if''' (head->data > key) 
&emsp;&emsp;'''return''' find(head->left, key); 
&emsp;'''if''' (head->data < key) 
&emsp;&emsp;'''return''' find(head->right, key); 
}

----

===Вставка===
====Алгоритм====
Вставку ключа, как и поиск, будем осуществлять рекурсивно, начиная из вершины.
# Если узел пустой, вставляем на его место новый узел с ключом.
# Если ключ равен значению в узле, возвращаемся и ничего не добавляем.
# Если ключ меньше значения в узле, рекурсивно вызываем вставку в левом поддереве.
# Если ключ больше значения в узле, рекурсивно вызываем вставку в правом поддереве.
====Реализация на языке C====
void insert (node_t* head, T key) { 
&emsp; '''if''' (head->data == key) 
&emsp;&emsp; '''return'''; 
&emsp; '''if''' (head->data > key) { 
&emsp;&emsp; '''if''' (head->left == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->left = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->left, key); 
&emsp; } 
&emsp; '''if''' (head->data < key) { 
&emsp;&emsp; '''if''' (head->right == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->right = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->right, key); 
&emsp; } 
}

----

===Удаление===
====Алгоритм====
[[Файл:BSTDelete.png|500 px|right|thumb|Удаление элемента с двумя детьми]]
Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
# Если вершина пуста, возвращаемся.
# Если значение в вершине больше ключа, вызываем удаление для левого поддерева.
# Если значение в вершине меньше ключа, вызываем удаление для правого поддерева.
# Если значение в вершине равно ключу, возможны следующие три случая:
## Правый и левый дети являются пустыми. Тогда просто удаляем узел, обнуляя указатель у родителя.
## Один из детей является пустым. В таком случае удаляем вершину, присоединяя ребёнка к родителю удалённого узла.
## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.

==Асимптотическая сложность операций==
Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.

Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

Файл:BSTDelete.png

2020-05-24T21:57:51Z

Algocourselecturenotes:

Наивное дерево поиска

2020-05-24T21:57:20Z

Algocourselecturenotes: /* Асимптотическая сложность */

==Определение и свойства==
'''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура данных двоичное дерево, для любого узла которого выполняются следующие свойства:
# Оба узла поддерева являются двоичными деревьями поиска;
# Все значения ключей левого поддерева меньше ключа узла;
# Все значения ключей правого поддерева больше ключа узла.
[[Файл:BST.png|200 px|right|thumb|Двоичное дерево поиска]]
==Операции над деревом==
===Поиск===
====Алгоритм====
Поиск узла по заданному ключу можно осуществлять рекурсивно, начиная из вершины.
# Если узел отсутствует, возвращаем нулевой указатель.
# Если значение в узле равно ключу, возвращаем указатель на узел.
# Если значение в узле больше ключа, запускаем поиск по ключу в левом поддереве.
# Если значение в узле меньше ключа, запускаем поиск по ключу в правом поддереве.
====Реализация на языке C====
node_t* find (node_t* head, elem_t key) { 
&emsp;'''if''' (!head) 
&emsp;&emsp;'''return''' ''NULL''; 
&emsp;if (head->data == key) 
&emsp;&emsp;'''return''' head; 
&emsp;'''if''' (head->data > key) 
&emsp;&emsp;'''return''' find(head->left, key); 
&emsp;'''if''' (head->data < key) 
&emsp;&emsp;'''return''' find(head->right, key); 
}

----

===Вставка===
====Алгоритм====
Вставку ключа, как и поиск, будем осуществлять рекурсивно, начиная из вершины.
# Если узел пустой, вставляем на его место новый узел с ключом.
# Если ключ равен значению в узле, возвращаемся и ничего не добавляем.
# Если ключ меньше значения в узле, рекурсивно вызываем вставку в левом поддереве.
# Если ключ больше значения в узле, рекурсивно вызываем вставку в правом поддереве.
====Реализация на языке C====
void insert (node_t* head, T key) { 
&emsp; '''if''' (head->data == key) 
&emsp;&emsp; '''return'''; 
&emsp; '''if''' (head->data > key) { 
&emsp;&emsp; '''if''' (head->left == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->left = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->left, key); 
&emsp; } 
&emsp; '''if''' (head->data < key) { 
&emsp;&emsp; '''if''' (head->right == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->right = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->right, key); 
&emsp; } 
}

----

===Удаление===
====Алгоритм====
Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
# Если вершина пуста, возвращаемся.
# Если значение в вершине больше ключа, вызываем удаление для левого поддерева.
# Если значение в вершине меньше ключа, вызываем удаление для правого поддерева.
# Если значение в вершине равно ключу, возможны следующие три случая:
## Правый и левый дети являются пустыми. Тогда просто удаляем узел, обнуляя указатель у родителя.
## Один из детей является пустым. В таком случае удаляем вершину, присоединяя ребёнка к родителю удалённого узла.
## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.
[[Файл:BST.png|200 px|right|thumb|Удаление элемента с двумя детьми]]

==Асимптотическая сложность операций==
Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.

Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

Наивное дерево поиска

2020-05-24T21:56:50Z

Algocourselecturenotes: /* Операции над деревом */

==Определение и свойства==
'''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура данных двоичное дерево, для любого узла которого выполняются следующие свойства:
# Оба узла поддерева являются двоичными деревьями поиска;
# Все значения ключей левого поддерева меньше ключа узла;
# Все значения ключей правого поддерева больше ключа узла.
[[Файл:BST.png|200 px|right|thumb|Двоичное дерево поиска]]
==Операции над деревом==
===Поиск===
====Алгоритм====
Поиск узла по заданному ключу можно осуществлять рекурсивно, начиная из вершины.
# Если узел отсутствует, возвращаем нулевой указатель.
# Если значение в узле равно ключу, возвращаем указатель на узел.
# Если значение в узле больше ключа, запускаем поиск по ключу в левом поддереве.
# Если значение в узле меньше ключа, запускаем поиск по ключу в правом поддереве.
====Реализация на языке C====
node_t* find (node_t* head, elem_t key) { 
&emsp;'''if''' (!head) 
&emsp;&emsp;'''return''' ''NULL''; 
&emsp;if (head->data == key) 
&emsp;&emsp;'''return''' head; 
&emsp;'''if''' (head->data > key) 
&emsp;&emsp;'''return''' find(head->left, key); 
&emsp;'''if''' (head->data < key) 
&emsp;&emsp;'''return''' find(head->right, key); 
}

----

===Вставка===
====Алгоритм====
Вставку ключа, как и поиск, будем осуществлять рекурсивно, начиная из вершины.
# Если узел пустой, вставляем на его место новый узел с ключом.
# Если ключ равен значению в узле, возвращаемся и ничего не добавляем.
# Если ключ меньше значения в узле, рекурсивно вызываем вставку в левом поддереве.
# Если ключ больше значения в узле, рекурсивно вызываем вставку в правом поддереве.
====Реализация на языке C====
void insert (node_t* head, T key) { 
&emsp; '''if''' (head->data == key) 
&emsp;&emsp; '''return'''; 
&emsp; '''if''' (head->data > key) { 
&emsp;&emsp; '''if''' (head->left == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->left = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->left, key); 
&emsp; } 
&emsp; '''if''' (head->data < key) { 
&emsp;&emsp; '''if''' (head->right == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->right = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->right, key); 
&emsp; } 
}

----

===Удаление===
====Алгоритм====
Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
# Если вершина пуста, возвращаемся.
# Если значение в вершине больше ключа, вызываем удаление для левого поддерева.
# Если значение в вершине меньше ключа, вызываем удаление для правого поддерева.
# Если значение в вершине равно ключу, возможны следующие три случая:
## Правый и левый дети являются пустыми. Тогда просто удаляем узел, обнуляя указатель у родителя.
## Один из детей является пустым. В таком случае удаляем вершину, присоединяя ребёнка к родителю удалённого узла.
## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.
[[Файл:BST.png|200 px|right|thumb|Удаление элемента с двумя детьми]]

==Асимптотическая сложность==
Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.

Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

Наивное дерево поиска

2020-05-24T21:56:05Z

Algocourselecturenotes:

==Определение и свойства==
'''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура данных двоичное дерево, для любого узла которого выполняются следующие свойства:
# Оба узла поддерева являются двоичными деревьями поиска;
# Все значения ключей левого поддерева меньше ключа узла;
# Все значения ключей правого поддерева больше ключа узла.
[[Файл:BST.png|200 px|right|thumb|Двоичное дерево поиска]]
==Операции над деревом==
===Поиск===
====Алгоритм====
Поиск узла по заданному ключу можно осуществлять рекурсивно, начиная из вершины.
# Если узел отсутствует, возвращаем нулевой указатель.
# Если значение в узле равно ключу, возвращаем указатель на узел.
# Если значение в узле больше ключа, запускаем поиск по ключу в левом поддереве.
# Если значение в узле меньше ключа, запускаем поиск по ключу в правом поддереве.
====Реализация на языке C====
node_t* find (node_t* head, elem_t key) { 
&emsp;'''if''' (!head) 
&emsp;&emsp;'''return''' ''NULL''; 
&emsp;if (head->data == key) 
&emsp;&emsp;'''return''' head; 
&emsp;'''if''' (head->data > key) 
&emsp;&emsp;'''return''' find(head->left, key); 
&emsp;'''if''' (head->data < key) 
&emsp;&emsp;'''return''' find(head->right, key); 
}
===Вставка===
====Алгоритм====
Вставку ключа, как и поиск, будем осуществлять рекурсивно, начиная из вершины.
# Если узел пустой, вставляем на его место новый узел с ключом.
# Если ключ равен значению в узле, возвращаемся и ничего не добавляем.
# Если ключ меньше значения в узле, рекурсивно вызываем вставку в левом поддереве.
# Если ключ больше значения в узле, рекурсивно вызываем вставку в правом поддереве.
====Реализация на языке C====
void insert (node_t* head, T key) { 
&emsp; '''if''' (head->data == key) 
&emsp;&emsp; '''return'''; 
&emsp; '''if''' (head->data > key) { 
&emsp;&emsp; '''if''' (head->left == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->left = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->left, key); 
&emsp; } 
&emsp; '''if''' (head->data < key) { 
&emsp;&emsp; '''if''' (head->right == ''null'') { 
&emsp;&emsp;&emsp; node_t* newnode = node_create(key); 
&emsp;&emsp;&emsp; newnode->parent = head; 
&emsp;&emsp;&emsp; head->right = newnode; 
&emsp;&emsp;&emsp; '''return'''; 
&emsp;&emsp; } 
&emsp;&emsp; insert(head->right, key); 
&emsp; } 
}
===Удаление===
====Алгоритм====
Удаление вершины по ключу будем также осуществлять рекурсивно, начиная из вершины.
# Если вершина пуста, возвращаемся.
# Если значение в вершине больше ключа, вызываем удаление для левого поддерева.
# Если значение в вершине меньше ключа, вызываем удаление для правого поддерева.
# Если значение в вершине равно ключу, возможны следующие три случая:
## Правый и левый дети являются пустыми. Тогда просто удаляем узел, обнуляя указатель у родителя.
## Один из детей является пустым. В таком случае удаляем вершину, присоединяя ребёнка к родителю удалённого узла.
## Оба ребёнка присутствуют. В таком случае находим элемент u, следующий за удаляемым (для этого, начиная с правого ребёнка удаляемого, совершаем проход влево), и помещаем его значение в удаляемый элемент, после чего удаляем элемент u.
[[Файл:BST.png|200 px|right|thumb|Удаление элемента с двумя детьми]]
==Асимптотическая сложность==
Асимптотическая сложность операций поиска, вставки и удаления составляет O(h), где h - высота дерева.

Отметим при этом, что в худшем случае возможно вырождение дерева в список (например, при последовательном добавлении элементов отсортированного массива), в связи с чем возникает потребность в балансировке дерева, осуществляемой в различных видах деревьев поиска (Декартово дерево, АВЛ-дерево, Splay-дерево, Красно-чёрное дерево, B-дерево).

Наивное дерево поиска

2020-05-24T19:39:02Z

Algocourselecturenotes: Новая страница: «==Определение и свойства== '''Двоичное дерево поиска''' (англ. - ''Binary Search tree - BST'') - структура д…»

Файл:BST.png

2020-05-24T18:38:52Z

Algocourselecturenotes:

Дерево отрезков

2020-05-15T09:57:06Z

Algocourselecturenotes: /* Пример задачи */

== Общая идея ==
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева. 
''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table''

== Структура ==
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки.
[[Файл:vis_tree.png]]
 
Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n). 

== Обработка запроса ==
Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая: 
1. TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. 
2. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящая вершина" думала над тем, что с этим знанием делать. 
3. TreeSeg ⋂ QuerySeg ≠ ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

{{Template:Lemma
|What = Лемма 1
|Statement = Каждый такой запрос выполняется за O(log n).
|Proof = Понятно, что оценка асимптотики алгоритма сводится к подсчету количества рекурсий, которые наша процедура потребует для выполнения. Рассмотрим произвольный уровень нашего дерева при запросе. На нем мы сделаем не более двух рекурсий вниз по дереву (случай 3). Таким образом, количество рекурсий ограничено O(1) * O(height) = O(log n).
}}

== Изменение дерева ==
''Замечание: на данном этапе предлагается перейти к произвольной функции f элементов на отрезке. Разумеется, нам подойдут не все функции. Необходимо, чтобы эта функция была ассоциативной, поскольку иначе мы не сможет "расставлять скобки" при сведении этой задачи к меньшим. '' 
''Оговорка: мы храним наше дерево в виде массива - по аналогии с бинарной кучей. '' 
Итак, обрабатываем запрос вида change (i, new_value). Существуют два подхода: 
1. "Изменение снизу". 
Зная номер вершины i мы можем пересчитать все значения дерева, которые идут на пути от корня до этой вершины (напомним, что индекс родителя при нашей оговорке мы найдем как i / 2). Эта схема плоха тем, что работает только для случая, когда количество элементов - степень двойки. 
2. "Изменение сверху". 
Аналогично процедуре обработки запроса, мы рекурсивно спускаемся в нужное нам поддерево, переподсчитываем там нашу функцию, после этого обновляем значение в текущей вершины и возвращаем его.
 

== Изменение элементов на подотрезке ==
Пусть нам поступает запрос на присвоение всем элементам с индексами от L до R значения new_value. Вновь применим идею отложенной операции. Будем рекурсивно спускаться от корня пока весь соответствующий текущей вершине полуинтервал не будет лежать в [L, R); когда это произошло, сохраним в этой вершине запрос на изменение. 
Тогда нужно понять, как это повлияет на процедуру обработки запроса. Разумеется, изменится случай 1 - сейчас нам придется учитывать не только значение вершины, но и эту отложенную операцию, что, впрочем, несильно усложняет дело. Также необходимо в случае 3 "протолкнуть" отложенную операцию в сыновей. Понятно, что никакую асимптотику это нарушить не может. Но здесь важно не забыть после рассмотрения случаев 1, 2, 3 обновить значение в текущей вершине на основе вновь полученной информации о листьях данной вершины. И только после этого можно безопасно возвращаться к родительскому узлу.

== Персистентное дерево отрезков ==
''Замечание: здесь нам придется отказаться от идеи хранить структуру в виде массива, по аналогии с бинарной кучей.'' 
Вдобавок к уже известным функциям и требованием иногда хочется уметь возвращаться к старой версии дерева. Таким образом, мы хотим добавить функцию checkout (version_number), где version_number - количество вызовов функции изменения дерева на подотрезке. 
Заметим, что при каждом вызове функции изменения дерева на подотрезке изменяется лишь O(log n) вершин.
 
[[Файл:ветвь.png]]
 
Более того, при каждой такой операции изменяется лишь один путь от корня до листа. Итак, мы может создавать новую версию этого пути, возвращая из функции change указатель на новую версию того самого пути. Тогда в каждой вершине на этом пути один из детей будет обновленным, а другой старым. 
Имея на руках систему контроля версий, мы можем считать нашу функцию f от полуинтервала исходного массива не только в актуальной версии дерева, но и в любой его версии, имея массив, в котором индекс - номер версии, а значение - соответствующая подветвь.

== Пример задачи ==
Имеется статический массив. Запрос - количество элементов с индексами из [L, R), которые лежат во множестве {x, x+1, ... y-1, y}. 
'''Способ 1.''' 
Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. 
'''Способ 2.''' 
Отсортируем элементы по возрастанию (разумеется, с сохранением первоначальной позиции элементов), получив массив S. Создадим пустой массив того же размера E, сделаем на нем дерево отрезков. После этого будем пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого достаточно сделать count (L, R, "≤ y") - count (L, R, "< x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая. 

''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

Дерево отрезков

2020-05-15T09:56:55Z

Algocourselecturenotes: /* Пример задачи */

== Общая идея ==
Очень похоже на sparse table - хотим предподсчитывать какие-то значения для отрезков, и обновлять их при изменении дерева. 
''Замечание: рассматриваем на примере задачи RMQ из конспекта про sparse table''

== Структура ==
На нижнем уровне располагаются элементы массива, на уровень выше - узлы, в которых минимум из двух элементов, на уровень выше - минимум из соответствующих соседей предыдущего уровня и так далее. Рисунок для случая, когда количество элементов в массиве - степень двойки.
[[Файл:vis_tree.png]]
 
Разумеется, уровней всего O(log n). На i-м уровне, начиная от самого нижнего, n / 2^i элементов. Таким образом, все дерево можно построить (просто сумма членов геометрической прогрессии) за O(n). 

== Обработка запроса ==
Общая идея: процедура getMin начинает от корня дерева и рекурсивно спускается в те отрезки, которые ее интересуют. Пусть мы находимся в вершине x, которая соответствует полуинтервалу TreeSeg = [L_tree, R_tree), а нам нужен минимум на полуинтервале QuerySeg = [L_q, R_q). Строго говоря, возможны три случая: 
1. TreeSeg ⊆ QuerySeg. Тогда необходимо вернуть значение из вершины. 
2. TreeSeg ⋂ QuerySeg = ∅. Необходимо вернуть какую-то большую константу IntMax, или какой-то флаг, показывающий, что отрезки не пересекаются - чтобы уже "вышестоящая вершина" думала над тем, что с этим знанием делать. 
3. TreeSeg ⋂ QuerySeg ≠ ∅. Тогда, разумеется, для обработки запроса необходимо вернуть min (getMin (left_half (x)), getMin (right_half (x))). Заметим, что в силу того что left_half и right_half не пересекаются, мы в будущем сможем решать более сложные задачи с помощью этой же структуры.

{{Template:Lemma
|What = Лемма 1
|Statement = Каждый такой запрос выполняется за O(log n).
|Proof = Понятно, что оценка асимптотики алгоритма сводится к подсчету количества рекурсий, которые наша процедура потребует для выполнения. Рассмотрим произвольный уровень нашего дерева при запросе. На нем мы сделаем не более двух рекурсий вниз по дереву (случай 3). Таким образом, количество рекурсий ограничено O(1) * O(height) = O(log n).
}}

== Изменение дерева ==
''Замечание: на данном этапе предлагается перейти к произвольной функции f элементов на отрезке. Разумеется, нам подойдут не все функции. Необходимо, чтобы эта функция была ассоциативной, поскольку иначе мы не сможет "расставлять скобки" при сведении этой задачи к меньшим. '' 
''Оговорка: мы храним наше дерево в виде массива - по аналогии с бинарной кучей. '' 
Итак, обрабатываем запрос вида change (i, new_value). Существуют два подхода: 
1. "Изменение снизу". 
Зная номер вершины i мы можем пересчитать все значения дерева, которые идут на пути от корня до этой вершины (напомним, что индекс родителя при нашей оговорке мы найдем как i / 2). Эта схема плоха тем, что работает только для случая, когда количество элементов - степень двойки. 
2. "Изменение сверху". 
Аналогично процедуре обработки запроса, мы рекурсивно спускаемся в нужное нам поддерево, переподсчитываем там нашу функцию, после этого обновляем значение в текущей вершины и возвращаем его.
 

== Изменение элементов на подотрезке ==
Пусть нам поступает запрос на присвоение всем элементам с индексами от L до R значения new_value. Вновь применим идею отложенной операции. Будем рекурсивно спускаться от корня пока весь соответствующий текущей вершине полуинтервал не будет лежать в [L, R); когда это произошло, сохраним в этой вершине запрос на изменение. 
Тогда нужно понять, как это повлияет на процедуру обработки запроса. Разумеется, изменится случай 1 - сейчас нам придется учитывать не только значение вершины, но и эту отложенную операцию, что, впрочем, несильно усложняет дело. Также необходимо в случае 3 "протолкнуть" отложенную операцию в сыновей. Понятно, что никакую асимптотику это нарушить не может. Но здесь важно не забыть после рассмотрения случаев 1, 2, 3 обновить значение в текущей вершине на основе вновь полученной информации о листьях данной вершины. И только после этого можно безопасно возвращаться к родительскому узлу.

== Персистентное дерево отрезков ==
''Замечание: здесь нам придется отказаться от идеи хранить структуру в виде массива, по аналогии с бинарной кучей.'' 
Вдобавок к уже известным функциям и требованием иногда хочется уметь возвращаться к старой версии дерева. Таким образом, мы хотим добавить функцию checkout (version_number), где version_number - количество вызовов функции изменения дерева на подотрезке. 
Заметим, что при каждом вызове функции изменения дерева на подотрезке изменяется лишь O(log n) вершин.
 
[[Файл:ветвь.png]]
 
Более того, при каждой такой операции изменяется лишь один путь от корня до листа. Итак, мы может создавать новую версию этого пути, возвращая из функции change указатель на новую версию того самого пути. Тогда в каждой вершине на этом пути один из детей будет обновленным, а другой старым. 
Имея на руках систему контроля версий, мы можем считать нашу функцию f от полуинтервала исходного массива не только в актуальной версии дерева, но и в любой его версии, имея массив, в котором индекс - номер версии, а значение - соответствующая подветвь.

== Пример задачи ==
Имеется статический массив. Запрос - количество элементов с индексами из [L, R), которые лежат во множестве {x, x+1, ... y-1, y}. 
'''Способ 1.''' 
Будем в каждой вершине хранить весь соответсвующий массив в отсортированном виде. Кажется, что о памяти лучше не думать, но на самом деле все относительно прилично: каждый элемент находится от корня на расстоянии O(log n) вершин, поэтому всего дополнительно затрачено будет O(n log n). После этого необходимо найти наибольший элемент, меньший x и наименьший, больший y в массиве нужной вершины. Тогда нужно просто вернуть количество элементов между этими только что найденными. 
'''Способ 2.''' 
Отсортируем элементы по возрастанию (разумеется, с сохранением первоначальной позиции элементов), получив массив S. Создадим пустой массив того же размера E, сделаем на нем дерево отрезков. После этого будем пробегать по массиву S и ставить в массив E единицы в соответствии и сохраненным ранее порядком. После этого достаточно сделать count (L, R, "≤y") - count (L, R, "<x"), используя описанную выше систему контроля версий. Памяти мы тратим по-прежнему O(n log n), поскольку у нас n разных ветвей по log(n) каждая. 

''Замечание: можно сделать дерево отрезков из деревьев отрезков, чтобы эффективно отвечать на похожие запросы в случае плоскости. ''

2020-05-14T23:34:41Z

Algocourselecturenotes: /* Алгоритм */

'''Breadth-first search''' (сокр. '''BFS''', рус. ''Поиск в ширину'', ''Обход в ширину'') - один из алгоритмов обхода графа. Является довольно простым и эффективным. Часто используется для поиска кратчайшего пути в графе.

==Задача==

Пусть задан неориентированный граф ''G = (V, E)''. Пусть все ребра имеют одинаковый вес, равный, например, ''1''. Пусть также задана некоторая начальная вершина ''S''. Пусть ''расстояние между вершинами'' - сумма весов рёбер, по которым нужно пройти, чтобы попасть из одной вершины в другую. И пусть, наконец, нужно найти кратчайшее расстояние от начальной вершины до всех остальных. Решим задачу, используя '''BFS'''.

==Алгоритм==

===Лемма I===
Кратчайшие пути в графе образуют дерево.

''Доказательство'':

2020-04-30T16:49:24Z

Algocourselecturenotes: /* Задача о гамильтоновом цикле */

2020-04-30T16:24:32Z

Algocourselecturenotes:

ДП на подмножествах

2020-04-30T16:23:31Z

Algocourselecturenotes: /* Описание проблемы */