这题是一个简单的二维数组操作题,简单是因为,这个和你在网上找到的介绍一维树状数组的操作差不多,只不过这个是二维的而已。
对于一个二维的树状数组,你可以这样认为:是一个一维数组,但是每个元素又是一个一维数组,也就是一维数组套一维数组。
那么更新时,可以认为是更新每个一维数组的值,但是一维数组又是一个一维数组,那么还得更改里面的一维数组的值。
那么update函数就变成了下面的代码:
update
同样的求和函数read()就会变成如下代码:
read
对于这两个函数理解了之后,这题就是一个很简单的题了,update函数不用变,但是求和时就要改变了,不过也不能叫改变,因为,求和时会用到上面的read函数。但是所要求是一个矩形,也就是不一定是从(1,1)开始。那么我们可以变成四个矩形的和或者差,比如我们要求sum(x1,y1,x2,y2)时我们可以变成read(r,t)-read(l-1,t)-read(r,b-1)+read(l-1,b-1)。也就是大矩形减去两个小矩形然后再加一个多减去的矩形。