Help me know this technique!!!

Revision en1, by Hd7, 2019-08-14 11:55:14

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-08-14 11:55:14 824 Initial revision (published)