自动搬运

查看原文

来自洛谷，原作者为

	阮行止 算法+网络安全研究者，致力于推动 OI 教育的进步

搬运于2025-08-24 21:48:34，当前版本为作者最后更新于2016-09-25 19:15:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

n*n的矩阵，每次给一个子矩阵 区间+1 。最后输出整个矩阵。

优化。用二维线段树或二维树状数组完成上面的操作。

复杂度单次$O(log^2n)$ ，总复杂度 $O(mlog^2n+n^2)$，足以吊打此题。

但是NOIP是不会考二维数据结构的

考虑这个问题的一维版：一个序列，最开始全是 0 .每次区间加 1 ,最后输出每个数。

于是有一种叫做“差分”的奇技淫巧：

假设我们现在要给[2,5]这个区间加一。原来的序列是：

0 0 0 0 0 0 0 0

这时候我们在2上面打 +1 标记， 6 上面打 -1 标记。那么现在的序列是：

0 +1 0 0 0 -1 0

有什么用呢？从左往右扫描这个数组，记录当前经过的标签之和。这个和就是对应那个数的答案。

这样，对于每个区间加操作，只需要O(1) 的时间打上标记。

最后扫描输出即可。

现在把问题拓展到二维。假设我们要覆盖[(2,2),(5,5)] ，那么标记便可以这样打：

0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0

即在每一行都按照一维的方式来操作

int sum=0,i,j;
   for(i=1;i<=n+1;i++)
      for(j=1;j<=n+1;j++)
         sum+=flag[i][j],real[i][j]=sum;

之后 real 数组里就存了最后的矩阵。输出即可。

这个算法的复杂度是每次打标记O(n) ，总复杂度是O(mn+n^2)