标签：fir   number   write   维护   and   comment   space   script   tar   

HihoCoder1336 Matrix Sum

描述

You are given an N × N matrix. At the beginning every element is 0. Write a program supporting 2 operations:

\1. Add x y value: Add value to the element Axy. (Subscripts starts from 0

\2. Sum x1 y1 x2 y2: Return the sum of every element Axy for x1 ≤ x ≤ x2, y1 ≤ y ≤ y2.

输入

The first line contains 2 integers N and M, the size of the matrix and the number of operations.

Each of the following M line contains an operation.

1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000

For each Add operation: 0 ≤ x

For each Sum operation: 0 ≤ x1 ≤ x2

输出

For each Sum operation output a non-negative number denoting the sum modulo 109+7.

样例输入

5 8
Add 0 0 1
Sum 0 0 1 1
Add 1 1 1
Sum 0 0 1 1
Add 2 2 1
Add 3 3 1
Add 4 4 -1
Sum 0 0 4 4 

样例输出

1
2
3 

题解

题意

查询、修改二维数组中的相关值。

思路

二维树状数组维护所有操作，二维树状数组的相关操作与一维几乎完全相同。

代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

HihoCoder1336 Matrix Sum（树状数组）

标签：fir   number   write   维护   and   comment   space   script   tar   

原文地址：https://www.cnblogs.com/caomingpei/p/9520198.html