Add amounts to 2 rectangles of a 4 x 6 grid of zeros without touching every cell. Each rectangle becomes four corner marks in a difference grid: a start at its top-left, stops past its right edge and below its bottom edge, and a restart where those two stops would cancel twice. A prefix pass along rows and then down columns turns the marks back into the rectangles. The extra stop row and column catch edges at the border.
A 5 by 7 difference grid, all zero.
Rectangle rows 0 to 2, columns 1 to 3, +5. Four writes: +5 at (0,1) starts it. -5 at (0,4) stops it past the right edge. -5 at (3,1) stops it below the bottom. +5 at (3,4) cancels the corner that both stops would hit.
Rectangle 1: four corner writes.
Rectangle rows 1 to 3, columns 2 to 5, +2. Four writes: +2 at (1,2) starts it. -2 at (1,6) stops it past the right edge. -2 at (4,2) stops it below the bottom. +2 at (4,6) cancels the corner that both stops would hit.
Rectangle 2: four corner writes.
Row 0, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 0 is now 0, 5, 5, 5, 0, 0.
Row 0 prefixed.
Row 1, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 1 is now 0, 0, 2, 2, 2, 2.
Row 1 prefixed.
Row 2, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 2 is now 0, 0, 0, 0, 0, 0.
Row 2 prefixed.
Row 3, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 3 is now 0, -5, -5, -5, 0, 0.
Row 3 prefixed.
Row 4, prefix along the row: each cell adds the one to its left, so a start spreads right until its stop cancels it. Row 4 is now 0, 0, -2, -2, -2, -2.
Row 4 prefixed.
Column 0, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 0 is now 0, 0, 0, 0.
Column 0 prefixed.
Column 1, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 1 is now 5, 5, 5, 0.
Column 1 prefixed.
Column 2, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 2 is now 5, 7, 7, 2.
Column 2 prefixed.
Column 3, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 3 is now 5, 7, 7, 2.
Column 3 prefixed.
Column 4, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 4 is now 0, 2, 2, 2.
Column 4 prefixed.
Column 5, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 5 is now 0, 2, 2, 2.
Column 5 prefixed.
Column 6, prefix down the column: each cell adds the one above, so a row's spread continues down until the stop row cancels it. Column 6 is now 0, 0, 0, 0.
Column 6 prefixed.
The top-left 4 x 6 block holds every rectangle's sum. 2 rectangles cost 4 writes each plus one pass over the grid, O(k + R x C), instead of O(k x R x C) for filling each rectangle cell by cell.
Final grid computed.