Hd7's blog

By Hd7, history, 2 months ago, , 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. Comments (12)
 » 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
 » 2 months ago, # | ← Rev. 2 →   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