移动电话--二维树状数组

题目描述:

Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S´S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix.

 

Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area.

输入格式:

输入包括若条指令，每条指令占一行。

指令以0开头，表示初始化一个区域，初始值为0

指令以1开头，表示修改某个格子的值。

指令以2开头，询问一个区间的累加和。

指导以3开头，表示结束。

具体参加下表。

 

指令	参数	说明
0	S	初始矩阵的大小为 S´S ，并被初始化为0。该指令只出现在最头部。
1	X Y A	Add A to the number of active phones in table square (X, Y). A may be positive or negative.
2	L B R T	累加所有的 (X,Y)的值，其中 L £ X £ R, B £ Y £ T
3		结束整个程序，该指令只会出现在最后。

 

输入的数值总是合法的，不需要检测。另外修改的A可以是负数，所以某个位置的数可能会被修改成0以下。

给定的矩形区域下标是从0开始的，若一个区域 4´4, 具体的下标是0 £ X £ 3 和 0 £ Y £ 3。

 

输出格式:

如果指令不是2不需要回答任何问题。

如果指令是2，那么你的程序需要输出一个整数，并加以换行。

样例输入:

0 1
1 0 0 28766
2 0 0 0 0
1 0 0 -2826
2 0 0 0 0
1 0 0 -587
2 0 0 0 0
1 0 0 1017
2 0 0 0 0
1 0 0 -17234
2 0 0 0 0
1 0 0 19618
2 0 0 0 0
1 0 0 -2237
2 0 0 0 0
1 0 0 -9192
2 0 0 0 0
1 0 0 -11132
2 0 0 0 0
1 0 0 1842
2 0 0 0 0
3

样例输出:

28766
25940
25353
26370
9136
28754
26517
17325
6193
8035

提示:

 二维的树状数组。

矩阵大小<=1024

指令数<=60010

时间限制: 1000ms
空间限制: 128MB

---