Структуры данных (23 сентября 2019)

  1. [20 минут] Избавляемся от амортизации
    1. Вектор. Ленивое копирование: когда переполнились начинаем копировать по одному элементу
    2. Вектор. Ленивое копирование: заранее начинаем копировать по одному элементу и выделять память
    3. Хеш-таблица. Ленивое копирование.
    4. Очередь с минимумом на двух стеках (тоже избавляемся от амортизации). Реализация через два динамических массива.

  2. [25 минут] Куча
    1. Вводная задача: есть дела, у них есть приоритеты; появляются новые дела, нужно иногда делать наиболее приоритетную задачу.
    2. Интерфейс (базовый): add, extractMin; интерфейс (расширенный): del, decreaseKey.
    3. Бинарная куча: реализация на массиве через siftUp → decreaseKey, add; siftDown → extractMin, del
    4. Бинарная куча: build за O(n) (док-во sum k/2k уже было в практике)
    5. Обратные ссылки (пример: массив с операциями a[i]=x, min на всём массиве, вводная задача: у i-го дела иногда меняется приоритет)
    6. Min = Max (+1 на -1, меньше на больше)
    7. heapsort = build + ExtractMin*n
    8. Преобразование операций: decreaseKey = del + add; del = decreaseKey + exractMin
− Перерыв −
  1. [22 минут] Пополняемые структуры данных. Преобразование операций.
    1. Find → Del. Удалить X из структуры, умеющей только Find : пометить, как удалённый. (пример из прошлого: хеш-таблица с открытой адресацией)
    2. Учим priority_queue делать Del: храним отдельно две кучи − добавленные элементы, удалённые элементы.
    3. Add → Merge. Сливаемые структуры: меньшее к большему (учим кучи и хеш-таблицы сливаться)
    4. Merge → Add. Add − просто частный случай Merge.
    5. Build → Add. Пополняемый массив: добавить X, посчитать количество X от L до R.
      1. [5 минут] Корневая. Предподсчёт за O(nlogn), добавление за O(n1/2), запрос за 2logn.
      2. [10 минут] Предподсчёт за O(nlogn), запрос за log2n. Добавление нового элемента = пополняемые структуры.
    6. Build → Add → Del. Удалить X из структуры с аддитивным запросом (хранить две структуры = добавленные элементы + удалённые)

  2. [15 минут] Аллокация памяти
    1. Общие слова: в C++ память откуда-то берётся. Локальное на стеке, глобальное и через new из heap-а. Научимся делать что-то такое же ручками, иногда эффективнее.
    2. [5 минут] Стек + рекурсия (освобождать можно только последнее выделенное). Доп.пример: когда пишем на c++ можно в деструктор засунуть финализатор и дёрнуть из него наш delete.
    3. [5 минут] Список + куски одного размера (пример: двусвязный список, хеш-таблица на списках) + кеширование
    4. [5 минут] Сложное решение общей задачи аллокации (только идея, без технические подробностей): куча свободных кусков и указатели на следующий/предыдущий.
    5. В с++ : new = наш аллокатор, delete = empty

  3. [skipped] [10 минут] Два указателя и ответы на запросы в offline
    1. [skipped] Число различных чисел на отрезке li ≤ li+1, ri ≤ ri+1. O(n+m).
    2. [skipped] Отрезки произвольны. Алгоритм Мо. O(nm1/2).