Теория

1. Частичные суммы (задача = sum[L,R])
2. Частичные минимумы (задача = min[1,R])
3. Метод двух указателей (задача = пересечение, объединение, разность множеств)
4. Подсчет count[x] (задача, есть массив из чисел от 0 до 10⁶, нужно за O(1) говорить "сколько раз в нем встречалась число x")
5. Разница Online и Offline задач.

Задачи

1. Сумма на подрямоугольнике за O(1)
2. Минимум в углу прямоугольника O(1)
3. Даны числа -1 и 1, нужно определить, сколько подотрезков имеют нулевую сумму.
1. Для отрезка за O(N)
2. Для окружности за O(N)
4. Нужно за O(N) найти подотрезок с максимальной суммой.
1. Для отрезка за O(N)
2. С ограничением на длину отрезка Len > A за O(N)
3. С ограничением на длину отрезка B > Len > A за O(N)
4. На окружности
5. Выбрать отрезок с max суммой, содержащий не менее K различных чисел.
6. Задача Hard: длины от L до R, число различных чисел от A до B, все это на окружности, максимизировать сумму