Compute matrix trace and support updates

Given an n x n integer matrix M, implement a function trace (M) that returns the sum of its main diagonal. Follow-ups: (a) If you receive q point updates (i, j, val) changing M[i][j] to val, design a data structure to return the current trace after each update in O(1) time; (b) Extend the function to also compute the anti-diagonal sum efficiently; (c) Discuss time and space complexities and edge cases (non-square input, large n).

Part 1: Compute the main diagonal trace of a square matrix

Given an integer matrix matrix, return the sum of its main diagonal, from top-left to bottom-right. If the matrix is empty, return 0. If the matrix is not square, return None.

Constraints

• 0 <= n <= 2000, where n is the number of rows
• -10^9 <= matrix[i][j] <= 10^9
• If the matrix is non-empty, it should be square for a valid input

Examples

Example 1

Input: ([[1, 2], [3, 4]],)
Output: 5

Explanation: The main diagonal is 1 and 4, so the sum is 5.

Example 2

Input: ([[7]],)
Output: 7

Explanation: A 1x1 matrix has exactly one diagonal element.

Hints

1. The main diagonal consists of entries where the row index equals the column index.
2. Before summing, verify that every row has length n.

Part 2: Support O(1) trace queries after point updates

You are given an n x n integer matrix matrix and a list of point updates. Each update is a tuple (i, j, val) meaning matrix[i][j] becomes val using 0-based indexing. Return a list where the k-th value is the current main diagonal trace after applying the k-th update. Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return None.

Constraints

• 0 <= n <= 2000
• 0 <= q <= 200000, where q is the number of updates
• -10^9 <= matrix[i][j], val <= 10^9
• Updates use 0-based indices

Examples

Example 1

Input: ([[1, 2], [3, 4]], [(0, 1, 10), (1, 1, 7), (0, 0, -1)])
Output: [5, 8, 6]

Explanation: The first update is off-diagonal, so the trace stays 5. Then 4 becomes 7, making the trace 8. Finally 1 becomes -1, making the trace 6.

Example 2

Input: ([[5]], [(0, 0, 3), (0, 0, 3)])
Output: [3, 3]

Explanation: A 1x1 matrix's only cell is always on the main diagonal.

Hints

1. Do not recompute the whole trace after each update. Store the current trace in a variable.
2. Only updates with i == j change the trace, and the change is val - old_value.

Part 3: Maintain both main-diagonal and anti-diagonal sums under updates

You are given an n x n integer matrix matrix and a list of point updates. Each update is a tuple (i, j, val) meaning matrix[i][j] = val with 0-based indexing. After every update, return both the main diagonal sum and the anti-diagonal sum as a pair (main_sum, anti_sum). Your solution should do O(1) work per update after initialization. If the initial matrix is not square, or any update index is out of bounds, return None. Note: in an odd-sized matrix, the center cell belongs to both diagonals.

Constraints

• 0 <= n <= 2000
• 0 <= q <= 200000
• -10^9 <= matrix[i][j], val <= 10^9
• Updates use 0-based indices
• For anti-diagonal positions, i + j == n - 1

Examples

Example 1

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], [(0, 2, 10), (1, 1, 0), (2, 0, -1)])
Output: [(15, 22), (10, 17), (10, 9)]

Explanation: The first update changes only the anti-diagonal. The second update hits the center, so it changes both sums. The third update changes only the anti-diagonal.

Example 2

Input: ([[1, 2], [3, 4]], [(0, 0, 5), (0, 1, 7)])
Output: [(9, 5), (9, 10)]

Explanation: In a 2x2 matrix, (0,0) is on the main diagonal only, while (0,1) is on the anti-diagonal only.

Hints

1. Keep two running sums: one for the main diagonal and one for the anti-diagonal.
2. When n is odd, the center cell satisfies both i == j and i + j == n - 1, so one update may affect both sums.