二维树状数组

题目描述

“第一分钟，X说，要有矩阵，于是便有了一个里面写满了0的n×m矩阵。
第二分钟，L说，要能修改，于是便有了将左上角为(a,b)，右下角为(c,d)的一个矩形区域内的全部数字加上一个值的操作。
第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。
第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。
第五分钟，和雪说，要有耐心，于是便有了时间限制。
第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”
——《上帝造裸题的七分钟》
所以这个神圣的任务就交给你了。

输入格式

输入数据的第一行为X n m，代表矩阵大小为n×m。
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作：

• L a b c d delta —— 代表将(a,b),(c,d)为顶点的矩形区域内的所有数字加上delta。
• k a b c d —— 代表求(a,b),(c,d)为顶点的矩形区域内所有数字的和。

请注意，kk为小写。

输出格式

针对每个k操作，在单独的一行输出答案。

输入输出样例

输入 #1

1
2
3
4

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3

输出 #1

1

12

解析

不多说了。。。

就是一个支持矩阵的子矩阵加减、子矩阵和查询的树状数组模板题

讲解见这里吧

代码实现

代码也不放了。。上面的链接给的代码就是这题的 AC 代码