I read many people's solutions and I realized the technique that helps me count effectively. This technique is:

If i want to increase all elements in range $$$[l;r]$$$ in array $$$cnt[]$$$, i will set $$$cnt[l]++$$$ and $$$cnt[r+1]--$$$, after that i will calculate cumulative sum from left to right, $$$cnt[i]+= cnt[i-1], \forall i \in [1:n]$$$.

The same approach is applied for 2d counting arrray. If i want to increase every cell in rectangle with top-left $$$(x_1, y_1)$$$ and bottom-right $$$(x_2, y_2)$$$. I will set` cnt[x1][y1]++; cnt[x1][y2+1]--; cnt[x2+1][y1]--; cnt[x2+1][y2+1]++; `

and then calculate the partial sum of this 2d counting array.

I want to get more information for this technique. Could you help me the name of it or any link that is relevant. Thanks in advance.

I don't think there's a specific name for it. But, you build a difference array. This technique is mentioned in Competitive Programmer's Handbook.

Is the book written by Antti Lâksonen? Omg i have downloaded it before, is this technique in advance chapter that i have not covered yet?

It's on page 93, under

`Range Updates`

.Thank you very much!!

This is just prefix sum

Prefix sum is the work after we set ++, —-. I want to know more about the origin of this technique.

I don't know its name either. I often call it difference array($$$b_i=a_i-a_{i-1}$$$). If $$$b$$$ is $$$a$$$'s difference array, then $$$a$$$ is $$$b$$$'s prefix sum array.

We can do lots of things with it.

For example, a classic problem, you are given an integer sequence $$$a$$$ with length $$$n$$$, then following $$$q$$$ operations, either add a number to $$$[l,r]$$$, either query the GCD of $$$[l,r]$$$. If we consider $$$a$$$'s difference array $$$b$$$, then the first operation is quite easy. For the second operation, $$$\gcd(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,a_{l+1}-a_l,\dots,a_r-a_{r-1})=\gcd(a_l,b_{l+1},\dots,b_r)$$$. Just build a segment tree of $$$b$$$, every time calculate $$$a_l$$$ and $$$\gcd(b_{l+1},\dots,b_r)$$$.

For another example, 1110E magic stone. See more in the editorial. It's kinda beautiful.

Thank man a lot, i will try it.

It's just common sense for a considerate amount of coders. Don't need to think so hard about it, you've got a mind-blow experience.

I see it so magical, i want to get more insights on it. Why do you say that? That I don’t understand clearly something makes me discomforts

You can also consider

`a[l]++, a[r+1]--`

as`add[l]++, remove[r]++`

(maybe it's better for understanding)It's called Mars' Trick in Romania