Excuse me, can I ask everyone a question?. As I know, we can calculate sum of a sub-rectangle in a 2D-matrix in O(1) by pre-calculating a 2D-Prefix sum. So I wonder that: are there any way to calculate sum of a sub-rhombus (with R radius) in O(1) by pre-calculating? . I am a new member, sorry for any mistakes. Thanks in advance! 
1 Like
I don’t get what you exactly mean by radius of rhombus, can you clarify a bit ?
1 Like
you should attach proper problem link and detail.
Don’t just be afraid.
Happy Coding…
I don’t find any major difference in pre-calculation of a rectangle or a rhombus, because what you do to pre-calculate rectangle sum is cover the points lying in the range of the rectangle in each iteration for each possible rectangle.
All you need to do is change the conditions you used to pre-calculate the sum of desired rectangle to the conditions to cover all points on rhombus you need for all possible rhombuses.
Will this help ?
I’m assuming you’re talking about a sub-rhombus that looks like the one below. If so, you can just shift each row by an offset, then reduce the problem to the sub-rectangle sum problem.
Original (rhombus)
---******
--******-
-******--
******---
Shift each row by an offset (becomes a rectangle)
---******
--******-
-******--
******---