I and Amoo_Safar always discuss our lazy segment tree logic.
The difference is this:
When I enter a node, I first apply its pending lazy value to the node itself.
But Amoo_Safar's assumption is that when he enters a node, the lazy value has already been applied before.
Below I show how this difference appears in implementation.
Amoo_Safar's style
In this style, the node is considered already updated correctly. The lazy value only means that this effect still has to be pushed to the children later.
So before going deeper, we call shift(id).
void upd(int id, int val) {
seg[id] += val;
lazy[id] += val;
}
void shift(int id) {
if (!lazy[id]) return;
upd(id << 1, lazy[id]);
upd(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int ql, int qr, int val) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {
upd(id, val);
return;
}
shift(id);
int mid = (l + r) >> 1;
update(id << 1, l, mid, ql, qr, val);
update(id << 1 | 1, mid, r, ql, qr, val);
seg[id] = pull(seg[id << 1], seg[id << 1 | 1]);
}
My style
In this style, when I enter a node, I do not assume its pending lazy has already been applied to the node itself.
So the first step is to call shift(id, l, r) and make the node clean at that moment.
void shift(int id, int l, int r) {
if (!lazy[id]) return;
seg[id] += lazy[id];
if (r - l > 1) {
lazy[id << 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
}
lazy[id] = 0;
}
void update(int id, int l, int r, int ql, int qr, int val) {
shift(id, l, r);
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) {
lazy[id] += val;
shift(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, ql, qr, val);
update(id << 1 | 1, mid, r, ql, qr, val);
seg[id] = pull(seg[id << 1], seg[id << 1 | 1]);
}
Both are correct. The main difference is just the invariant you keep in your head while writing the code.
Which one do you use, and why?
