Issues/questions on segment tree beats' "lazy_update"

[kuroni]

Hi, so I was looking around for an example segment tree beats' implementation, and I stumbled upon yours.

After some time looking at the code, I noticed that lazy_update is always INT64_MAX. I think this is a bug in your implementation (I believe lazy_update should be assigned with g instead of INT64_MAX in tag<UPDATE>). However, the fact that lazy_update is never used means that it is not necessary in the first place.

I believe this is the case because the only times tag<UPDATE> are used apart from during construction and pushdown are inside tag<CHMIN> and tag<CHMAX>. Let's take tag<CHMIN> for example, the condition g <= a[i].min is actually always false if a[i].min != a[i].max (i.e. if the range has more than one value), because that will make the tag condition of CHMIN false (if g <= a[i].min then g cannot be larger than a[i].max_second). Therefore, the condition is only true iff a[i].min == a[i].max, and when that is the case then the push down of CHMIN has already taken care of updating the values of the children.

That's all of my issue on lazy_update, and sorry for the wall of text.