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

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

1) Прибавить $$$x$$$ на прямоугольнике $$$[x1, x2], [y1, y2]$$$, помимо ассоциативности операция должна быть коммутативна, например присваивание не подойдёт.

2) Посчитать сумму на прямоугольнике $$$[x1, x2], [y1, y2]$$$.

Почему нельзя использовать пуши? Для массовых операций с пушами должно быть выполнено свойство, что отложенная операция может складываться, но в случае 2Д ДО мы должны складывать не числа, а отрезки, и их объединять уже не получиться. Но помимо пушей есть другой тип массовых операций.

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

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

Номер корня равен 0, реализация на полуинтервалах

void upd(int l, int r, int lx, int rx, int v, int x) {
    if (l >= rx || r <= lx) return;
    sum[v] += (min(r, rx)-max(l, lx)) * x;

    if (l >= lx && r <= rx) {
        add[v] += x;
        return;
    }
    int m = (l + r) / 2;
    upd(l, m, lx, rx, v*2+1, x);
    upd(m, r, lx, rx, v*2+2, x);
}

Теперь запрос суммы. Чтобы узнать актуальную сумму в вершине, нужно взять сумму $$$add[p]$$$ по всем предкам, умноженную на длину отрезка, и $$$sum[v]$$$. Чтобы лучше понять, почему это так, попробуйте посчитать сумму для красной вершины на картинке. Функция запроса будет такой же, как и в обычном ДО, только нужно поддерживать сумму на пути от корня до вершины.

В реализации можно даже не поддерживать сумму на пути, а просто когда мы спускаемся добавлять к ответу $$$add[v] \cdot (min(r, rx)-max(l, lx))$$$, это равносильно тому, что описано выше. Позже именно такой способ будет использоваться для больших размерностей.

int ask(int l, int r, int lx, int rx, int v) {
    if (l >= rx || r <= lx) return 0;
    if (l >= lx && r <= rx) {
        return sum[v];
    }
    int m = (l + r) / 2;
    return ask(l, m, lx, rx, v*2+1) + ask(m, r, lx, rx, v*2+2) + (min(r, rx)-max(l, lx)) * add[v];
}

Теперь этот же способ можно использовать для двумерного ДО.

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