前缀和，差分，尺取

常规
1

前缀和

  • 可以减少处理时间
//使用sum数组记录和。
sum[i] = sum[i-1] + a[i];
//a~b之间所有数的和。
cout << sum[b] - sum[a - 1];

二维前缀和

//使用sum数组记录和。
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
//a1,b1~a2,b2之间所有数的和。
cout << sum[a2][b2] - sum[a1 - 1][b2] - sum[a2][b1 - 1] + sum[a1 - 1][b1 - 1];

一维差分

//求出a的差分数组
for(int i = 1; i <= n; i++)
    a[i] -= a[i - 1];
a[l] += 5;
a[r + 1] -= 5;
//再求前缀和
for(int i = 1; i <= n; i++)
    a[i] += a[i - 1];

二维差分

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
	    	sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
	}
sum[x1][y1]+=5;
sum[x2+1][y1]-=5;
sum[x1][y2+1]+=5;
sum[x2+1][y2+1]-=5;
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
	    	sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	}

双指针

for(int i=1,j=1;i<=n;i++){
	    	while(sum<s&&j<=n){
	    		sum+=a[j];
	    		j++;
			}
			if(sum>=s) mmin=min(mmin,j-i);
			sum-=a[i];
		}
1 个赞