我试图从一个 NXM 的矩阵中找到任何子矩阵 AXB 的最大元素。我实现了稀疏树方法,但是无法优化它。事实上,我需要解决范围查询的问题,因此需要优化代码。在进行预计算时,对于任何 N、M 值,时间复杂度为 O(NMlog(N)log(M))。如何将其改进为 (N*M)。这是我的预计算代码:
for(int i=0; i<n;i++)
for(int j=0; j<m;j++)
cin>>arr[i][j];
for(int i=0; pow(2,i) <= n; i++)
for(int j=0; pow(2,j) <= m; j++)
for(int x=0; x + pow(2,i)-1 < n; x++)
for(int y = 0; y + pow(2,j) -1 < m; y++)
{
i=(int)i;
j=(int)j;
if (i == 0 && j == 0)
M[x][y][i][j] = arr[x][y];
else if (i == 0)
M[x][y][i][j] = maxi(2,M[x][y][i][j-1], M[x][(int)(y+pow(2,(j-1)))][i][j-1]);
else if (j == 0)
M[x][y][i][j] = maxi(2,M[x][y][i-1][j], M[(int)(x+ pow(2,(i-1)))][y][i-1][j]);
else
M[x][y][i][j] = maxi(4,M[x][y][i-1][j-1], M[(int)(x + pow(2,(i-1)))][y][i-1][j-1], M[x][(int)(y+pow(2,(j-1)))][i-1][j-1], M[(int)(x + pow(2,(i-1)))][(int)(y+pow(2,(j-1)))][i-1][j-1]);
}
对于输入的x、y、x1和y1
k = log(x1 - x + 1);
l = log(y1 - y + 1);
int max_element = max(4,M[x][y][k][l], M[(int)(x1 - pow(2,k) + 1)][y][k][l], M[x][(int)(y1 - pow(2,l) + 1)][k][l], M[(int)(x1 - pow(2,k) + 1)][(int)(y1 - pow(2,l) + 1)][k][l]);
如何提高此代码的性能。请帮忙。