Questions about updating Two Dimensional Binary Indexed Tree (2D BIT)?

Revision en5, by wonderful_trip, 2021-02-20 11:52:00

When learning about 2D BIT, I have the question that 2D BIT can be easily updated 1 element and get sum, but can update the range ?

Problem:

for each query, you need to update the rectangle (x, y, u, v) each coordinate of a rectangle with upper left corner (x, y) and lower right corner being (u, v) incremented by c "at the same time".

After the update, we can find the sum query (x1,y1,x2,y2);

For example:

Sum(2,3,3,4) is 28;

Is it possible to solve this problem? If so, please show how to do it!!!

thanks for help!!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English wonderful_trip 2021-02-20 11:52:00 6 Tiny change: 'query (x1,x2,y1,y2);\n\nF' -> 'query (x1,y1,x2,y2);\n\nF'
en4 English wonderful_trip 2021-02-20 11:51:06 85 Tiny change: '1.png)\n\nsum(\n\nIs it ' -> '1.png)\n\nSum(2,3,3,4) is 28;\n\nIs it '
en3 English wonderful_trip 2021-02-20 10:12:53 20 Tiny change: 'ented by c.\n\nFor e' -> 'ented by c "at the same time".\n\nFor e'
en2 English wonderful_trip 2021-02-20 08:43:46 88 Tiny change: 'ange ?\n\nfor ea' -> 'ange ?\n\nProblem:\n\nfor ea'
en1 English wonderful_trip 2021-02-20 08:33:46 497 Initial revision (published)