$ Структуры данных (2 пары) # Терминология ## Online, Offline ## Static data, Dynamic data ## Амортизированное время работы, real time ## get-запрос, change-запрос # Базовые структуры ## Стек, очередь, дек, вектор. Интерфейсы. Без индексации за O(1) и с индексацией. ## Односвязные списки (поддерживает 3 операции), двусвязные списки (поддерживает 4 операции) ## Массивы → очередь, дек ## Вектор: массив с push\_back за амортизированную O(1) ## Вектор за O(1) без амортизации ## Хеш-таблица на основе списков
Перевыделение памяти, неамортизированное O(1), в C++ и Java амортизированное
HashSet, HashMap, сказать, что есть ключ, что есть значение ## Частичные суммы: sum[L,R) = s[R] - s[L], s[0] = 0 ## Отсортированный массив + бинарный поиск (здесь же рассказать про три разных бинарных поиска: (0, 1) и (-1, position) и lower\_bound ## set<int>, map<int, int> (только описание интерфейсов) # Задачи ## [sort, hash table] Найти число различных чисел в массиве ## [hash table, map] Числа добавляются и удаляются. После каждого запроса в online говорить, сколько различных чисел в мультимножестве.
Тут же показываем, что Add → Build и разницу offline и online. ## [vector,array] Дек, но размер заранее не известен, offline версия предыдущей задачи ## [list] Аллокатор кусков памяти константного размера ## [stack] Аллокатор кусков памяти произвольного размера, память мы не освобождаем
Конец первой пары
Здесь нужно напомнить все полученные интерфейсы и структуры: стек, очередь, дек, вектор, список, двусвязный, хеш-таблица, sorted array. Рассказать про get-запрос, change-запрос.
## [hash table, map] var := value (хранение значения от переменной)
Нужно научиться по string получать хеш типа int, далее hash table ## [sorted array, binary search] offline версия предыдущей задачи ## [стек] разбор арифметического выражения без скобок: +, -, *, /, ^ (два стека, левоассоциативность) ## [стек] разбор арифметического выражения со скобками: +, -, *, /, ^ (скобка -- не операция, заодно выражение теперь можно взять в скобки) ## [стек] проверка скобочной последовательности на правильность, несколько видов скобок, разбиение скобок на пары: pair[i] # Преобразование операций ## merge → add (add и есть merge) ## add → merge (меньшее к большему, пример: set, hash table) ## find/ничего → delete (пометить, как удаленное, пример: хеш-таблица с открытой адресацией) ## build, get → add, merge (пополняемые структуры, static → dynamic, пример: sorted array & lower\_bound) ## build, get → add, delete (отдельно хранить множество удаленных, операция "кол-во x: L ≤ x ≥ R") # Задачи ## [find → delete] Хеш-таблица с открытой адресацией с удалением
Конец второй пары
## [add → merge] Дано корневое дерево, в вершинах числа. Посчитать количество различных чисел в каждом из поддеревьев. ## [build → add, del] Упражняемся с Ахо-Корасиком, который за O(Σ|s_i|) строит и за O(|text|) говорит число вхождений: научимся добавлять и удалять строки. ## [static → dynamic] Множество точек, поддерживать размер выпуклой оболочки, точки добавляются.