Зимняя школа 2022: Руслан Масальский: Дерево отрезков
Лекция студента ОНУ Руслана Масальского (команда ONU_PRIMATES) (базовый уровень) в рамках Зимней Школы Looksery 2022 по олимпиадному программированию. ОНУ им Мечникова, 26.01.2022, в 14:00 1) Контест — в группе codeforces "Зимняя школа Looksery" по адресу https://codeforces.com/group/j3uuUV7Hld/contests 2) Страница Зимней Школы в группе Google — https://groups.google.com/g/acm-onu-facult/c/APXivMtv8v0/m/nwavexa2DAAJ План 1. Интро. Задача сумма на отрезке (префиксный массив) переход к задаче сумма на отрезке . 2. Построение дерева отрезков на сумму. Два подхода построения. Дополнение нулями или же классический. build 3. Научимся искать сумму get sum, merge 4. Изменение в точке. Покраска + добавление. update 5. Изменение на отрезке. Покраска + добавление. update range, push 6. Аналогичные деревья на максимум, минимум, ксор, gcd, произведение по модулю. 7. Поиск k единицы. Каскадный спуск. 8. Задачи: a. Количество инверсий b. Количество уникальных на отрезке c. Подотрезок наибольшей суммы с изменением в элементе+ запрос ответа на отрезке d. Сжатие массива для решения задачи количество инверсий для произвольного массива. Дополнительные материалы: 1. Дерево отрезков. Построение — Викиконспекты Университета ИТМО https://neerc.ifmo.ru/wiki/index.php?title=Дерево_отрезков._Построение 2. MAXimal :: algo :: Дерево отрезков https://e-maxx.ru/algo/segment_tree 3. Википедия — Дерево отрезков https://ru.wikipedia.org/wiki/Дерево_отрезков
Лекция студента ОНУ Руслана Масальского (команда ONU_PRIMATES) (базовый уровень) в рамках Зимней Школы Looksery 2022 по олимпиадному программированию. ОНУ им Мечникова, 26.01.2022, в 14:00 1) Контест — в группе codeforces "Зимняя школа Looksery" по адресу https://codeforces.com/group/j3uuUV7Hld/contests 2) Страница Зимней Школы в группе Google — https://groups.google.com/g/acm-onu-facult/c/APXivMtv8v0/m/nwavexa2DAAJ План 1. Интро. Задача сумма на отрезке (префиксный массив) переход к задаче сумма на отрезке . 2. Построение дерева отрезков на сумму. Два подхода построения. Дополнение нулями или же классический. build 3. Научимся искать сумму get sum, merge 4. Изменение в точке. Покраска + добавление. update 5. Изменение на отрезке. Покраска + добавление. update range, push 6. Аналогичные деревья на максимум, минимум, ксор, gcd, произведение по модулю. 7. Поиск k единицы. Каскадный спуск. 8. Задачи: a. Количество инверсий b. Количество уникальных на отрезке c. Подотрезок наибольшей суммы с изменением в элементе+ запрос ответа на отрезке d. Сжатие массива для решения задачи количество инверсий для произвольного массива. Дополнительные материалы: 1. Дерево отрезков. Построение — Викиконспекты Университета ИТМО https://neerc.ifmo.ru/wiki/index.php?title=Дерево_отрезков._Построение 2. MAXimal :: algo :: Дерево отрезков https://e-maxx.ru/algo/segment_tree 3. Википедия — Дерево отрезков https://ru.wikipedia.org/wiki/Дерево_отрезков