1.一维前缀和
sum[i]=sum[i-1] + a[i];
2.P2671 NOIP2015 普及组 求和(前缀和数组应用)
求和题解
2.二维前缀和(处理矩形的面积的权值)
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];(只用一个数组，防止爆空间)
1.P1719 最大加权矩形(二维前缀和遍历所有矩形)
2.P2004 领地选择(二维前缀和遍历固定大小矩形)
(二维前缀和遍历固定大小矩形,把每一个坐标看作矩形的一个块)
3.一维差分
i 到 j 加 k cf[i]+=k; cf[j+1]-=k; sum[i]=sum[i-1]+cf[i];
1.P3397 地毯(差分数组)
2.P3406 海底高铁(实际问题应用)
3.P2879 [USACO07JAN] Tallest Cow S(实际问题应用)
4.P4552 [Poetize6] IncDec Sequence
