Блог пользователя wonderful_trip

Автор wonderful_trip, история, 4 года назад, По-английски

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!!!

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

You can literally google up 2D bit and the first result shows exactly what you described.

Edit: I understand that I am wrong since I did not read the post properly. I deserved all the downvotes. In my defense tho, you can search up 2D BIT range sum range updates which also gives the results about the same topic.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Comments on

    https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/

    is sum (x, y, u, v)

    But it just tells us how to update an coordinates one by one.

    What I want is to update the all coordinates of a rectangle (x, y, u, v) of a rectangle with the top left corner (x, y) and the lower right corner being (u, v ) increment c at "the same time".

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

      So I'm assuming you are not familiar with 2D prefix sum. Let's again explain why the formula for getting the sum works. Let our subrectangle have the lower-left corner $$$(x_1, y_1)$$$ and the upper-right corner $$$(x_2, y_2)$$$. So for getting the sum, first we get the sum from origin to $$$(x_2, y_2)$$$, but then all number having $$$x$$$ less than $$$x_1$$$ or $$$y$$$ less than $$$y_1$$$ should not be counted, so then we subtract the sum from the origin to $$$(x_1 - 1, y_2)$$$, and then from the origin to $$$(x_2, y_1 - 1)$$$. But then all the number having $$$x < x_1$$$ and $$$y < y_1$$$ is now subtracted twice, while we only need them to be subtracted once, so we now add the sum from the origin to $$$(x_1 - 1, y_1 - 1)$$$.

      The trick is the same for the updating operation. First, we need to update from the origin to $$$(x_2, y_2)$$$ with the value $$$c$$$. Now we update all numbers from the origin to $$$(x_1 - 1, y_2)$$$ with the value $$$-c$$$, as well as all the numbers from the origin to $$$(x_2, y_1 - 1)$$$. And then finally we add the number from the origin to $$$(x_1 - 1, y_1 - 1)$$$ with $$$c$$$ again.

      Edit: the way I describe here is "range update" with "point query", so apparently is not the thing that you wanted.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Sorry, the question I was going to ask was not like that but I asked the question unknown.

        I understand the 2D prefix total. But I mean that after the update, when finding the sum in the above example in cell 3 4 will be 28, not equal to 7 as your way.

        Because what I want to ask is an update to find the totals query, not the point query.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

          Ok so, sorry for misunderstanding your problem. Until now I don't think there is an effective way to do that with BIT. I mean, does 1D BIT even have that kind of updating operation? If you want range-update with range-query in the 1D problem you probably end-up using segment tree with lazy-propagation.

          For the 2D problem, the lazy-propagation segment tree is even harder to implement (and I don't know if it possible tho, since I also tried once and failed).

          If you want alternatives, I think you should try to do things like, offline processing.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

This article describes how to do range update and sum query for $$$d$$$-dimensional BIT in $$$\mathcal{O}(4^d \log^d{n})$$$.

TLDR:

If you let $$$a_{i, j}$$$ to be the amount that was added to suffix rectangle of $$$(i, j)$$$, then the value at point $$$(x, y)$$$ is $$$A_{x, y} = \sum \limits_{i \le x, j \le y} a_{i, j}$$$.

Now, the prefix sum of $$$A$$$ can be expressed as:

\begin{equation} \sum \limits_{i \le x, j \le y} A_{i, j} = \sum \limits_{i \le x, j \le y} \sum \limits_{i_1 \le i, j_1 \le j} a_{i_1, j_1} = \sum \limits_{i \le x, j \le y} a_{i, j} (x-i + 1) (y-j + 1) \end{equation} The last equation is achieved by considering the contribution of each $$$a_{i, j}$$$ to the answer.

When you expand the brackets you get expressions like prefix sum of $$$a$$$, multiplied by some subset of indices, and by some constant. This values can be calculated, storing BIT for every subset of indices (e.g. $$$a_{i, j} \cdot i$$$). For range update and range sum you simply decompose every rectangle into prefix/suffix rectangles.