Help me know this technique!!!

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Hd7 2019-08-14 11:55:14 824 Initial revision (published)