Quant Memo
Coding/●●●●●

Submatrix PnL queries with 2-D prefix sums

You have a grid grid[i][j] holding trader i's PnL on day j. You must serve many queries of the form "total PnL over traders r1..r2 and days c1..c2 inclusive".

grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]
region(1, 1, 2, 2) -> 28      # 5 + 6 + 8 + 9

Answer each rectangle query in O(1)O(1) after O(rc)O(rc) preprocessing.

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions