How to do using Seg tree

#1
  1. Consider N boxes numbered 1 to N. Each box can house any number of chocolates. And initially all the boxes are empty.
  2. 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)
#2

Okay I am assuming you are familiar with the concept of lazy propagation.
So if you observe , then in your problem you are simply adding arithmetic progression on a range with first term equal to 1 and common difference equal to 1.
So a more generic problem would be

Consider two types of queries:

  • 1 l r k d = update range [ l , r ] with an arithmetic progression of first term k and difference d .
  • 2 l r = report sum of all elements in range [ l , r ].

So I’d do it by maintaining three values for each node, K [ i ] = first term of progression, D [ i ] = difference between consecutive terms of progression and S [ i ] = current sum of node. Then to update the sum for a certain node i of size sz with a progression of first value k and difference d , we would add . The update to first terms and differences is a simple addition. We only need to be careful about updating the first term when moving to the right in updates that cover multiple ranges. Lazy updates work in the same way.

This is the code for this problem https://ide.codingblocks.com/s/346432
In your problem we simply take k and d both equal to 1 in update operation.

#3

Facing difficulties in Lazy Part

#4

That’s why I said you need to practice lazy propagation because this is a basic operation as we keep track of everything influencing the sum lazily, the first term and the difference.
Maybe try out segment tree part from this https://codeforces.com/edu/course/2
It would be worth it and help you improve

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.