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?
The second one is faster because it saves one "multiplication" (a less clumsy explanation could be found here)
However, mentally I find it easier to think with the first invariant, as the laziness then has a pretty reasonable meaning of an operation applied to the whole subtree (opposed to the subtree without the root)
The second one also makes implementation easier, as shown in this blog
it doesn't seem that either of these blogs use the 2nd approach? The first blog is about push-free / lazytag segment trees, the second blog seems to be using the 1st approach only (otherwise we would not be seeing lines like:
if (l&1) res += t[l++]for the query operations)There is a dedicated section on implementation and optimization details, where the optimizations include switching the invariant
isn't this approach 1? (Amoo_Safar style)
okay.. the source of my confusion was that the approaches are introduced in the opposite order that they are provided code..
I don't think these two approaches can be ranked slower to faster independent of the underlying operations. Even if we consider only the number of arithmetic operations, for a tree of depth $$$h$$$ the second approach does $$$4h$$$ more lazy+lazy operations, while the first does $$$4h$$$-$$$6h$$$ more value+lazy operations. If elements are vectors and updates are multiplications by a matrix, the first would be faster.
#include <atcoder/lazysegtree>I use the first version. Simply because it was the natural way I coded lazy propagation for the first time, and I find it more intuitive.