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

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

  2. [25 минут] Куча
    1. Интерфейс: add, del, extractMin, decreaseKey.
    2. Бинарная куча: реализация на массиве через siftUp → decreaseKey, add; siftDown → extractMin, del
    3. Бинарная куча: build за O(n) (док-во sum k/2k уже было в практике)
    4. Обратные ссылки (пример: массив с операциями a[i]=x, min на всём массиве)
    5. Min = Max (+1 на -1, меньше на больше)
    6. heapsort = build + ExtractMin*n
    7. Преобразование операций: decreaseKey = del + add; del = decreaseKey + exractMin
− Перерыв −
  1. [30 минут] Аллокация памяти:
    1. сложность задачи, пример мощного решения: heap + hash_table
    2. стек + рекурсия; c++: рекурсия с финализатором и пример рекурсивной функции
    3. список + куски одного размера (пример: хеш-таблица на списках) + кеширование
    4. в с++ : new = наш аллокатор, delete = empty

  2. [15 минут] Пополняемые структуры данных
    1. Find → Del. Удалить X из структуры, умеющей только Find : пометить, как удалённый
    2. Ничего → Del. Хранить отдельно две структуры: добавленные элементы, удалённые.
    3. Add → Merge. Сливаемые структуры: меньшее к большему (учим кучи и хеш-таблицы сливаться)
    4. Пополняемый массив: добавить X, посчитать количество X от L до R.
      1. Предподсчёт за O(nlogn), запрос за O(logn). Добавление нового элемента = корневая.
      2. Предподсчёт за O(nlogn), запрос за O(logn). Добавление нового элемента = пополняемые структуры.
    5. Удалить X из структуры с аддитивным запросом (хранить две структуры = добавленные элементы + удалённые)

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