表格分析不同维的前缀和及差分
【表格分析不同维的前缀和及差分】
| 一维 | 二维 | |
| 前缀和 | cin>>a[i], s[i]=s[i-1]+a[i] （1≤i≤n） | s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j] |
| cin>>s[i], s[i]+=s[i-1] （1≤i≤n） | ||
| 区间和 | s[x2]-s[x1-1] （x2≥x1） | s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1] |
| 差分 | d[i]=a[i]-a[i-1] | d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1] |
| 差分后更新 | a[i]=d[i]+a[i-1] | a[i][j]=d[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1] |
| 区间操作转端点操作 | d[x1]+=c，d[x2+1]-=c （x2≥x1） | d[x1][y1]+=c; d[x1][y2+1]-=c; d[x2+1][y1]-=c; d[x2+1][y2+1]+=c; |
备注：长度为 k 的区间和的公式为 s[i]-s[i-k]
【图例助记二维前缀和及差分】
很多朋友反映，二维前缀和及差分的公式不好记。记都记不住，那就更谈不上应用了。
在这里给大家推荐一个技巧，保准记得牢靠。即，首先观察一维的公式，然后使用“斜十字法”的图例推衍记忆二维的公式。
例如，针对一维的“区间操作转端点操作 d[x1]+=c，d[x2+1]-=c （x2≥x1）”，那么其二维的形式是什么呢？步骤如下：
（1）由一维公式中的下标 x1、x2+1 推衍出二维的下标为 (x1, y1)、(x2+1, y2+1)。
（2）利用二维的下标 (x1, y1)、(x2+1, y2+1) 进行“斜十字法”绘图如下。
（3）在图例中，按照 ① ④ 操作为“+”，② ③ 操作为“-”的约定，可得二维的“区间操作转端点操作”的代码为：
d[x1][y1]+=c;
d[x1][y2+1]-=c;
d[x2+1][y1]-=c;
d[x2+1][y2+1]+=c;
注意：
本博客是自己创造的助记方法，仅供参考。这种助记方法以一维的形式为出发点，所以前提是必须牢记一维的形式。
原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/145282546
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！