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]--asadd[l]++, remove[r]++(maybe it's better for understanding)It's called Mars' Trick in Romania
Can you please provide link to the explanation how it works?
you can read this comment
This technique is very interesting, I got problems many times that solved by this, like in my online assessments.
you can read this comment