Дерево отрезков по сумме + бинпоиск спуском: минимальный префикс с суммой >= S?
Массив неотрицательных чисел с точечными обновлениями. Запрос: найти наименьший индекс r, такой что префиксная сумма a[0]+...+a[r] >= S. Понятно, что префиксные суммы монотонны, можно бинпоиск + query за O(log^2 n). Как сделать спуском за O(log n)?
2 ответа
Раз префиксные суммы неубывают (числа неотрицательны), спуск по дереву на сумму даёт O(log n). На каждом узле смотрим: если сумма левого поддерева уже >= S, ответ там; иначе вычитаем её и ищем в правом остаток S - sum_left.
long long t[4*N]; // сумма поддерева
// минимальный r с префиксной суммой >= S, или -1
int lower_prefix(int v, int tl, int tr, long long S) {
if (t[v] < S) return -1; // даже всё поддерево не дотягивает
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
if (t[2*v] >= S) return lower_prefix(2*v, tl, tm, S);
return lower_prefix(2*v+1, tm+1, tr, S - t[2*v]);
}
Вызов: lower_prefix(1, 0, n-1, S). Если вернулось -1 — суммы всего массива не хватает. Сложность O(log n) на запрос, O(log n) на точечное обновление.
Это строго быстрее, чем «std::lower_bound по виртуальному массиву префиксов + query», который даёт O(log^2 n): мы вшиваем бинпоиск прямо в структуру дерева. Числа должны быть неотрицательными, иначе монотонности префиксов нет и спуск некорректен.
Если префикс надо искать начиная не с 0, а с произвольного from, чистый спуск так просто не запускается. Тогда два варианта: (1) сначала pref = query(0, from-1), потом спуск с целью S + pref и проверкой >= from — но аккуратнее с границами; (2) проще — спуск с накоплением: идём по дереву и собираем сумму уже пройденных кусков слева от from, отсекая то, что левее from.
Частая ошибка: использовать этот приём, когда в массиве есть отрицательные значения. Префиксные суммы тогда не монотонны, lower_bound бессмыслен, и нужен совсем другой подход (например, дерево на минимум префиксов + спуск по нему). Всегда проверяйте знак данных перед тем, как полагаться на монотонность.