前缀和笔记
前缀和笔记
对于一个一维数组 a[m]
其前 i 项和记作 s[i]
如果想要对 a[m] 中任意连续段的值进行求和，例如 a[l]~a[r]
则可使用前缀和数组进行 o(n) 计算
int a[m],s[m];
s[0]=0;//定义s[0]的值，防止边界问题
for (int i=0;i<m;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
这样的话，s 数组中存储的值便是前 i 项 a 数组的和
a[l]~a[r] 则可写作 s[r]-s[l-1]，减少调用累加时间
若存在一个二维数组 a[m] [n]
求其前 i j 项的二维前缀和有公式：
s[i][j]=s[i][j-1]+s[i-1][j-1]-s[i-1][j-1]+a[i][j];
不难推出s[l1] [r1] ~ s[l2] [r2] 的和
对求任意的(l1,r1)~(l2,r2)有：
sum=s[l2][r2]-s[l2][r1]-s[l1][r2]+s[l1][r1];