Решим следующую задачу:

Дана таблица $$$n \cdot m$$$, поступают 2 вида запросов в онлайне:

1) Прибавить $$$X$$$ на прямоугольнике $$$[l1, r1], [l2, r2]$$$, помимо ассоциативности операция должна быть коммутативна, например присваивание не подойдёт.

2) Посчитать сумму (минимум, ...) на прямоугольнике $$$[l1, r1], [l2, r2]$$$.

Сначала разберём, как делать прибавление на отрезке и сумму на отрезке без пушей в одномерном ДО.

В каждой вершине будем хранить $$$sum[v]$$$ и $$$add[v]$$$ — сумму на отрезке и сколько мы прибавим каждому элементу на отрезке. Рассмотрим запрос прибавления: мы корректно пересчитаем все вершины, которые были посещены нашей функцией (на картинке желтые и зелёные), но сумма в вершинах ниже останется старой (красные), чтобы это исправить в тех вершинах, в которых остановилась функция (зелёные) сделаем $$$add[v] += x$$$.

Сделаем ДО по первой координате, в каждой вершине которого будет ДО на сумму, отвечающее за прямоугольник [l, r] [0, m]