Hard
Segment tree range updates with and without lazy propagation
A variant of the segment tree above needs to support 'add v to every element in range [l, r]' (a range update), not just point updates. The naive version below applies a range update by recursing down to every affected leaf individually. What is its worst-case complexity, and what does adding lazy propagation change?
main.cpp
void rangeUpdateNaive(int node, int start, int end, int l, int r, long long v) {
if (r < start || end < l) return;
if (start == end) { tree[node] += v; return; }
int mid = (start + end) / 2;
rangeUpdateNaive(2 * node, start, mid, l, r, v);
rangeUpdateNaive(2 * node + 1, mid + 1, end, l, r, v);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}10 of 46 in Data Structures & Algorithms