同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1635_二维树状数组1：单点修改，区间查询

2022-5-16 18:17| 发布者: Hocassian| 查看: 58| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950464204900-Problem List-采集的数据-后羿采集器.html

Pro.ID

1635

Title

二维树状数组 1：单点修改，区间查询

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1635

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

这是一道模板题。

给出一个 n × m 的零矩阵 A，你需要完成如下操作：

1 x y k ：表示元素 A_x,y 自增 k；
2 a b c d ：表示询问左上角为 (a, b) ，右下角为 (c, d) 的子矩阵内所有数的和。

输入

输入的第一行有两个正整数 n, m；

接下来若干行，每行一个操作，直到文件结束。

对于 10% 的数据，n = 1；

对于另 10% 的数据，m = 1；

对于全部数据，1 ≤ n, m ≤ 2¹² , 1 ≤ x, a, c ≤ n , 1 ≤ y, b, d ≤ m , |k| ≤ 10⁵ ，保证操作数目不超过 3×10⁵ ，且询问的子矩阵存在。

输出

Description

这是一道模板题。

给出一个 n × m 的零矩阵 A，你需要完成如下操作：

1 x y k ：表示元素 A_x,y 自增 k；
2 a b c d ：表示询问左上角为 (a, b) ，右下角为 (c, d) 的子矩阵内所有数的和。

Input

输入的第一行有两个正整数 n, m；

接下来若干行，每行一个操作，直到文件结束。

对于 10% 的数据，n = 1；

对于另 10% 的数据，m = 1；

对于全部数据，1 ≤ n, m ≤ 2¹² , 1 ≤ x, a, c ≤ n , 1 ≤ y, b, d ≤ m , |k| ≤ 10⁵ ，保证操作数目不超过 3×10⁵ ，且询问的子矩阵存在。

Output

对于每个 2 操作，输出一个整数，表示对于这个操作的回答。

Sample Input

2 2
1 1 1 3
1 2 2 4
2 1 1 2 2

Sample Output

样例输入