Similar presentations:
Алгоритмы и структуры данных. Специализированные структуры данных
1.
Алгоритмы иструктуры данных
Специализированные структуры данных
2.
STL - структурыhttps://ru.cppreference.com/w/cpp/container/
make_heap
priority_queue
map
multimap
set
multiset
bitset
3.
Постановка задачиинтервал
полуинтервал
Дана последовательность чисел A длины n (индексация с нуля):
a0, a1, a2, . . . , an−1.
Поступают запросы двух типов.
• Запрос модификации. Задан индекс i и число x. Нужно прибавить к i-му элементу
число x.
• Запрос суммы. Задана пара индексов l и r. Нужно вычислить сумму элементов на
полуинтервале [l, r), т. е. al + al+1 + . . . + ar−1, и вернуть результат.
(или найти максимальный/минимальный элемент на полуинтервале)
4.
Структуры данных для поиска наотрезке
1. Решение задачи «в лоб»:
1. Поиск за N
2. Модификация за 1 (для одного элемента)
2. Предпросчет:
1. Создадим второй массив в i-ом элементе которого будем хранить
значение функции для первых i элементов.
2. Поиск за 1 – F(a,b)=F(1,b)○F(1,a)
3. Модификация за N.
5.
частичная сумма или сумма на префиксе kрекуррентный подсчет:
Сумма элементов массива a на полуинтервале [l, r) равна разности
двух префиксных сумм sr и sl.
6.
последовательность (2, 1, 9, 7, 5, 2, 6)7.
Структуры данных для поиска на интервалеКорневая оптимизация
Дерево отрезков
Разреженная таблица
Декартово дерево
8.
Корневая оптимизация (Sqrtдекомпозиция)Основная идея sqrt-декомпозиции заключается в том, что сделаем следующий
предпосчёт: разделим массив на блоки длины примерно