### Loserinlife's blog

By Loserinlife, history, 3 months ago,

 » 3 months ago, # | ← Rev. 3 →   +8 I believe there are many solutions to this problem. Anyways, here is my approach.First, construct a "staircase" of size $m$ (full of 0s) on top of the grid then rotate everything 45 degrees counter-clockwise. Consider the sample :the link for the picture in case you can't see it : https://ibb.co/pRTYZFFIf you construct another staircase of size $m$, full of 0s, at the bottom of the rotated grid, you can see that the red paralellogram is actually a rectangular submatrix of a $(n + m) * m$ matrix.Any staircase can be represented as the difference of a green rectangle and a red "rectangle" as in the picture. More specifically, let $A$ be the original grid and $B$ be the $(n + m) * m$ grid, the green rectangle is $(1, c) - (r, c + h - 1)$ in $A$, while the red rectangle is $(1, c) - (m + r - c - h, c + h - 1)$ in $B$. (here I'm denoting a rectangle by its top-left and bottom-right points)We can use two 2D BITs to maintain $A$ and $B$ for the (sum of staircase) queries. For update queries $(r, c, v)$, update $[r][c] += v - A[r][c]$ in BIT $A$ and $[m + r - c][c] += v - B[m + r - c][c]$ in BIT $B$ and update the new values to $A[r][c]$ and $B[m + r - c][c]$.