Структуры данных (2 пары)

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