星星博客 »  > 

二维前缀和预处理减少二维数组计算相关时间复杂度

当需要计算矩阵中任意块的数值计算时,可以开辟额外数组提前存储好子块的和,再用子块和进行计算,可以减少遍历的步骤,实现O(1)复杂度进行计算。


// 定义一个额外数组map用于存储从矩阵11到以目标位置xy为右下角的那一块矩形的和
#include<iostream>
using namespace std;
int main()
{
	int x,y;
	int map[10][10]={0};
	int a[10][10]={0};
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=4;i++)
	{
		for(int j=1;j<=4;j++)
		{
			map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+a[i][j];//额外数组处理逻辑,应该很好看懂
		}
	}
	cin>>x>>y;//查询目标方块值的和
	cout<<map[x][y];
}

在这里插入图片描述

输入前五行,输出第六行,可见成功查询了a[3][2]块的和。

相关文章