Consider N boxes numbered 1 to N. Each box can house any number of chocolates. And initially all the boxes are empty.
There are two types of queries that can be posed by the throwers.
a. 0 l r -> Add chocolates to the boxes between the index l and r (inclusive) such that l'th box get 1 chocolate, (l+1)the box gets 2 chocolates ... r'th box gets (r-l+1) chocolate(s)
b. 1 l r -> Count the number of chocolates that are currently in the boxes between l and r (inclusive)
Can anyone provide some hints?
Auto comment: topic has been updated by bastard123 (previous revision, new revision, compare).
You can try out the problem here: https://cses.fi/problemset/task/1736
You could do this using segment tree with lazy propagation.
Just store the starting element of the sequence for current range [l,r] in lazy[v].
So while pushing this lazy value in the segment tree, it could be done :
segt[v] += (2*lazy[v] + r — l)*(r-l+1)/2; // sum of lazy[v], lazy[v]+1, lazy[v]+2.... upto r-l+1 elements
P.S: Just remember that while pushing lazy[v] to its children, you would need to pass the starting elements of their respective ranges as lazy values