# Snow-Cow Lazy Seg Tree

For this problem http://www.usaco.org/index.php?page=viewproblem2&cpid=973, 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);
B.upd(st[x],y*sub[x]);
}
``````

with

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

and

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

with

``````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.