9
правок
Изменения
Нет описания правки
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
# Предложите алгоритм с временем работы $O(n)$ для следующей задачи: задан массив из неотрицательных чисел и число $k$, определите число отрезков с суммой, не превышающей $k$. Также проанализируйте, работает ли ваш алгоритм, если массив может содержать отрицательные числа: постройте контрпример или докажите, что работает.
# Запросы на статическом массиве: задано число $k$ и запросы~{{--- отрезки }} посчитать ассоциативную необратимую функцию на отрезке длины от $k$ до $2k$. Ответ на запросы за $O(1)$ и препроцессинг за $O(n)$.# Запросы: 1. set(i, x) {{---}} $a[i] a_i := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y a_i \ge s$, $\sum\limits_{i=1}^{y - 1} a_i < s$ за $O(\log{n})$. # Обработайте $Qq$ запросов на прибавление на отрезке, получите конечный массивдлины $n$, за $O(Qn + q)$.
# Обработайте запросы за $O(\log{n})$. Первый {{---}} присвоить значение элементу, второй {{---}} задан отрезок, найти подотрезок с максимальной суммой, содержащийся в этом отрезке.
# Сведите задачу к запросам изменения в точке и функции на отрезке за $O(\log{n})$. Задача {{---}} отвечать на запросы: прибавление на отрезке и минимум на отрезке.
