【模板】二维树状数组 & LOJ #133 二维树状数组 1

题面

题目链接

这是一道模板题。

给出一个  的零矩阵 ,你需要完成如下操作:

  • 1 x y k:表示元素  自增 ;
  • 2 a b c d:表示询问左上角为 ,右下角为  的子矩阵内所有数的和。

思路

一维树状数组的扩展

我们知道,一维树状数组可以求一段区间的和,将其扩展到二维,对于一个矩阵,每一层可以看做一个数,实际上是树状数组,每次求到每一层时求出这一层的区间和即可。也就是两个一维树状数组套一套。

容斥思想

通过和树状数组一样的思路可以求出原点到目标点的子矩阵的和,和二维前缀和相同,利用容斥思想就可以求出任意子矩阵的和。具体如图,右下角浅色子矩阵的面积可以通过面积相减得到。

代码

 

暂无评论

发送评论


				
上一篇
下一篇