ЛКШ 2016. Группа A. День 3. Простенькие структуры данных.

  1. C++
    1. sort, merge
    2. set_union, set_difference
    3. lower_bound
    4. vector::resize
    5. partial_sum
  2. Фенвик
    1. Update в точке за O(logn)
    2. Поиск ассоциативной функции на префиксе за O(logn)
    3. Преимущества над деревом отрезков: нет дополнительной памяти, малая константа
    4. 2D-версия, 3D-версия
  3. Дерево отрезков
    1. Код. Построение за O(n), модификация в точке за O(logn), запрос на отрезке за O(log|R-L|)
    2. Релизация снизу: картинка с лесом
    3. Дерево отрезков сортированных массивов, 2D-запрос на статичном массиве за O(log2n)
  4. Задача: пусть есть структура, дающая "+" на отрезке, выразить через неё "+=" на отрезке.
  5. Большие координаты
    1. Offline и сжатие координат
    2. Динамическое дерево отрезков с запросами сверху
    3. Динамическое дерево отрезков с запросами снизу
    4. Динамическое дерево Фенвика
  6. Корневая
    1. По массиву. Задача: "Найти число элементов, равных x на отрезке. И += на отрезке."
    2. По запросам (отложенные операции). Перестраивать структуру каждые n1/2 шагов. Задача: "сколько числе от l до r? числа добавляются."
  7. Центроидная декомпозиция
    1. Выбор центра, рекурсивно от остаточных компонент. На выходе имеем parent[center], задающий дерево декомопозиции, и level[center]. Компонента центра v − вершины u : level[u] ≥ level[v] и они связны.
    2. Функция на пути (a, b): возьмём v = lca(a, b) в дереве декомопозиции. path[a,b] = path[a,v] + path[v,b], можно в min[level,v] хранить минимум на path[a,v]
    3. Минимум на пути за O(logn), за O(loglogn). Какие ещё функции умеем считать? Sum, Matrix Product, Gcd, Permutation Composition, кол-во смен цвета на пути.
    4. Количество путей длины ровно K.
    5. XOR на пути. Путь, на котором XOR равен S.
    6. Ближайшая вершина цвета c. Покраска одной вершины.