前缀和
作者:
ICE_TEA
,
2022-11-18 19:26:08
,
所有人可见
,
阅读 175
一维前缀和
int a[200000],s[200000]={0};//从1开始输入
for(int i = 1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]+=s[i-1]+a[i];
}
//输出
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
二维前缀和
int a[2000][2000]={0},s[2000][2000]={0};//从(1,1)开始输入
for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)scanf("%d",&a[i][j]);
for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
//输出
int t,y,g,h;cin>>t>>y>>g>>h;
printf("%d\n",s[g][h]+s[t-1][y-1]-s[t-1][h]-s[g][y-1]);