Идея lazy propagation: когда обновление на отрезке полностью покрывает узел, мы не спускаемся в детей, а ставим узлу отложенную пометку lazy[v] и сразу чиним его t[v]. Реальное проталкивание в детей делаем лениво — только когда нужно зайти глубже.
long long t[4*N], lazy[4*N];
void apply(int v, int tl, int tr, long long add) {
t[v] += add * (tr - tl + 1);
lazy[v] += add;
}
void push(int v, int tl, int tr) {
if (lazy[v]) {
int tm = (tl + tr) / 2;
apply(2*v, tl, tm, lazy[v]);
apply(2*v+1, tm+1, tr, lazy[v]);
lazy[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, long long add) {
if (l > r) return;
if (l == tl && r == tr) { apply(v, tl, tr, add); return; }
push(v, tl, tr);
int tm = (tl + tr) / 2;
update(2*v, tl, tm, l, min(r,tm), add);
update(2*v+1, tm+1, tr, max(l,tm+1), r, add);
t[v] = t[2*v] + t[2*v+1];
}
long long query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (l == tl && r == tr) return t[v];
push(v, tl, tr);
int tm = (tl + tr) / 2;
return query(2*v, tl, tm, l, min(r,tm))
+ query(2*v+1, tm+1, tr, max(l,tm+1), r);
}
Золотое правило: push вызывается перед спуском в детей и в update, и в query. После рекурсии в update пересобираем t[v] из детей. Сложность: O(log n) на операцию, O(n) память.
Переполнение: add * (tr - tl + 1) легко выскакивает за int — держите всё в long long.