Snow-Cow Lazy Seg Tree

For this problem, it appeared in the Range Updates Range Query module. However, after reading the solution, it appears to be 2 BITs instead of a Lazy SegTree. I wonder what is the Lazy Segtree solution to this problem? Or is the idea to substitute the BIT with a Lazy Segtree?

Good question. If we introduce an additional array arr where arr[i] denotes the colorfulness of snowball i, we can replace this function in the analysis:

void upd(int x, int y) {
	A.upd(st[x],y); A.upd(en[x]+1,-y);


void upd() {
    for (int i = st[x]; i <= en[x]; ++i) arr[i] += y;


cout << sub[x]*A.sum(st[x])+B.query(st[x]+1,en[x]) << "\n";.


ll sum = 0;
for (int i = st[x]; i <= en[x]; ++i) sum += arr[i];
cout << sum << "\n";

Any data structure that supports range increment range sum on arr will suffice. Let me know if that made sense.

Yes, that makes sense. Thank you.