Sum Query in 2D Immutable Array Dynamic Programming - rFronteddu/general_wiki GitHub Wiki
You are given a matrix and are tasked to enable retrieving the sum of a sub rectangle in linear time.
| --- | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 2 | 0 | -3 | 4 |
| 1 | 6 | 3 | 2 | -1 |
| 2 | 5 | 4 | 7 | 3 |
| 3 | 2 | -6 | 8 | 1 |
We observe that we can prepopulate a dynamic matrix, first we fill the first row and the first column, then we use the formula:
- d[i,j] = x[i,j] + d[i-1,j] + d[i,j-1] - d[i-1,j-1]
| --- | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 2 | 2 | -1 | 3 |
| 1 | 8 | 11 | 10 | 13 |
| 2 | 13 | 20 | 26 | 32 |
| 3 | 15 | 16 | 30 | 37 |
- We can ten calculate the sum of a sub rectangle (i1, j1), (i2,j2) using
- s = d[ $i_2$ , $j_2$] -
- ( $i_1$ > 0 ? d[ $i_1$ - 1, $j_2$] : 0) -
- ( $j_1$ > 0 ? d[ $i_2$, $j_1$ -1] : 0) +
- ($i_1$ > 0 && $j_1$ > 0 ? d[ $i_1$ - 1, $j_1$ - 1] : 0)