Можно ли выполнить обновление дополнения диапазона, добавив линейную функцию в дерево максимального сегмента?

Я полагаю, вы спрашиваете, можете ли вы сделать следующее обновление:
Учитывая обновление A B C, вы хотите добавить C ко всем элементам от A до B.

Проблема состоит в том, что обновление дерева сегмента обычно занимает O (N * logN) время, учитывая, что N — максимальное количество элементов. Тем не менее, ключевая идея реализации дерева сегментов заключается в том, что вы хотели бы предположить, что запросы диапазонов и что обычно вас интересуют не все диапазоны O (N ^ 2), а гораздо меньшее их подмножество.

Вы можете расширить диапазон обновлений, используя ленивое распространение Это обычно означает, что вы выполняете обновление, но вы не обновляете все узлы в дереве сегментов -> вы обновляете до некоторой точки, но вы не продолжаете дальше по дереву, так как оно не нужно.
Скажем, что вы обновили все до узла K, который отвечает за диапазон [10; 30] например. Позже вы выполните запрос «get info» [20; 40]. Очевидно, вам придется посетить узел K, но вас интересует не весь диапазон, а диапазон [20; 30], который на самом деле является его правильным потомком.
То, что вам нужно сделать, это «протолкнуть» обновление узла K к его левому дочернему элементу, а затем к его правому дочернему элементу и продолжить при необходимости.

В целом это будет означать, что при выполнении обновления вы будете выполнять обновление только до тех пор, пока не найдете подходящие узлы для интервала обновления, но не пойдете дальше. Это дает O (logN) время.
Затем при запросе вы продолжаете распространять обновления вниз по дереву, когда достигнете узла, для которого, как вы знаете, вы сохранили какое-то обновление для дальнейшего использования. Это также дает O (logN) время.

Немного хорошего материала: Ленивое распространение на сегментных деревьях