Алгоритмы и структуры данных. Специализированные структуры данных

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-декомпозиции заключается в том, что сделаем следующий
предпосчёт: разделим массив на блоки длины примерно