2D Fenwick tree

Write codeHard40 minCitadel style

Your task

Implement a 2D Fenwick (binary indexed) tree over a rows x cols grid initialized to zero. Process operations: ["set", r, c, v] adds v to cell (r, c); ["query", r1, c1, r2, c2] returns the sum of the inclusive sub-rectangle with corners (r1, c1) and (r2, c2) where r1<=r2 and c1<=c2. Return the list of query answers in order. Both operations must run in O(log(rows) * log(cols)).

Examples

matrix_sum_2d(rows: int, cols: int, ops: list) -> list[int]

Example 1

Input

matrix_sum_2d(3, 3, [["set", 0, 0, 5], ["set", 1, 1, 3], ["set", 2, 2, 2], ["query", 0, 0, 2, 2], ["query", 1, 1, 2, 2]])

Output[10, 5]