Конец Фурье и 2D. Строки. (10 апреля 2014)

  1. Деревья отрезков
    1. Реализация сверху (модификация на отрезке, отложанные операции) [code]
    2. 2D-дерево (дерево отрезков сортированных массивов) [code]
  2. Пишем Фурье
    1. Обратное: reverse(a + 1, a + n)
    2. Рекурсивная реализация с complex<double> [code]
    3. Предподсчитали все корни, уменьшили в два раза число умножений
    4. Нерекурсивная реализация [code] (нормальная версия) [code] (данная версия содержит излишнюю оптимизацию)
  3. Общие слова про строки
    1. КМП, Ахо-Корасик
    2. Z-функция
    3. Хеши, Бор
    4. Суф.структуры (массив, дерево, автомат)