Корневая с обновлениями

Статическая корневая полезна редко: обычно массив ещё и меняется. Хорошая новость в том, что обновления встраиваются почти без усилий.

Точечное изменение

Изменили $a[i]$ - испортился ровно один блок. Пересчитаем его сводку за $O(B)$:

void assign(int i, int value) {
    a[i] = value;
    int b = i / B;
    block[b] = NEUTRAL;
    for (int j = b * B; j < min(n, (b + 1) * B); j++) block[b] = combine(block[b], a[j]);
}

Для сумм пересчёт не нужен - достаточно поправить сводку на разность. Но для максимума он обязателен: если уменьшили как раз тот элемент, на котором достигался максимум, восстановить его без просмотра блока нельзя.

Это общее правило: обратимые операции обновляются за константу, необратимые - пересчётом блока.

Прибавление на отрезке

Здесь появляется вторая половина приёма - отложенная метка. Для каждого блока храним число $add[b]$: «ко всем элементам этого блока прибавлено столько-то, но в самом массиве это ещё не записано».

Тогда прибавление на отрезке разваливается так же, как запрос:

• целым блокам просто увеличиваем $add[b]$ - за $O(1)$ на блок;
• огрызки обновляем поэлементно и пересчитываем их блоки.

void add(int l, int r, int x) {
    int bl = l / B, br = r / B;
    if (bl == br) { for (int i = l; i <= r; i++) a[i] += x; rebuild(bl); return; }
    for (int i = l; i < (bl + 1) * B; i++) a[i] += x;  rebuild(bl);
    for (int b = bl + 1; b < br; b++) { addTag[b] += x; block[b] += x; }
    for (int i = br * B; i <= r; i++) a[i] += x;       rebuild(br);
}

Настоящее значение элемента - это $a[i] + add[i / B]$. Забыть прибавить метку при чтении - главная ошибка в этой конструкции, и проявляется она не всегда: пока запросы попадают в те же блоки, что и обновления, всё сходится.

Какие метки складываются

Метка «прибавить» складывается: две подряд дают сумму. Метка «присвоить» затирает предыдущую. Метка «прибавить, а потом присвоить» уже не сводится к одному числу, и такие пары надо разбирать отдельно.

Корневая тут снисходительнее дерева отрезков: если метки не складываются, всегда можно протолкнуть метку в блок - применить её ко всем $B$ элементам за $O(B)$ - и начать с чистого листа. В дереве отрезков проталкивание тоже есть, но там оно обязано быть дешёвым, а здесь $O(B)$ и так укладывается в бюджет запроса.

Сколько это стоит

операция	цена
запрос к отрезку	$O(\sqrt{n})$
точечное изменение	$O(1)$ или $O(\sqrt{n})$ с пересчётом
прибавление на отрезке	$O(\sqrt{n})$
присваивание на отрезке	$O(\sqrt{n})$

Все операции одного порядка - в этом удобство: не надо думать, какая из них дороже.