二维树状数组

题目描述

给$n \times m$个数$a_{1, 1}, a_{1, 2}, a_{1, 3}, \dots, a_{1, m}, \dots, a_{n, m}$。

支持$q$个操作：

1. 1 x y d，修改$a_{x,y} = d$。
2. 2 x y，查询$\sum_{i=1}^x \sum_{j = 1} ^ y a_{i, j}$。

输入格式

第一行三个整数$n, m, q (1\leq n,m\leq 500, q\leq 2 \times 10^5)$。

接下来$n$行每行$m$个整数$a_{1, 1}, a_{1, 2}, \dots, a_{1, m} ,\dots, a_{n, m} (1\leq a_{i, j}\leq 10^9)$。

接下来$q$行，每行一个形如1 x y d或者2 x y的操作，保证$1\leq x\leq n, 1\leq y \leq m, 1\leq d\leq 10^9$。

输出格式

对于每个查询，输出一行，表示答案。

样例输入

2 3 5
1 1 4
5 1 4
2 2 3
1 1 1 4
2 1 3
1 2 3 10
2 2 3

样例输出

16
9
25