前缀和笔记

前缀和笔记

对于一个一维数组 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];