Проверочный тест к предыдущим лекциям

1. Какая из задач "сложнее": найти гамильтонов путь в графе, найти простой путь максимальной длины в графе?
2. Придумайте структуру данных, которая умеет делать 2 операции: GetSum[L..R] и ко всем числам массива прибавить X.
3. Дан неорграф. Как проверить, правда ли, что существует 2 пути из A в B не пересекающихся по ребрам? за какое время это можно сделать?
4. Пусть у вас есть матрица NxN и N² времени на предподсчет
1. За какое время можно отвечать на запрос "сумма на прямоугольнике"?
2. За какое время можно отвечать на запрос "минимум на прямоугольнике"?
5. Пусть у вас есть массив длины N и NlogN времени на предподсчет
1. За какое время можно отвечать на запрос "сумма на отрезке"?
2. За какое время можно отвечать на запрос "минимум на отрезке"?
3. А если массив меняется?
6. Пусть вы умеете в дереве искать LCA(a, b) за O(1), за какое время можно найти
1. Сумму на пути в дереве?
2. Минимум на пути в дереве?