M x N 크기의 행렬이 주어지면 부분행렬 합계를 찾는 쿼리가 많이 있습니다. 쿼리에 대한 입력은 합계를 알아낼 하위 행렬의 왼쪽 상단 및 오른쪽 하단 인덱스입니다. 

부분행렬 합 쿼리가 O(1) 시간 내에 수행될 수 있도록 행렬을 전처리하는 방법. 

예:

  tli :   Row number of top left of query submatrix   tlj :   Column number of top left of query submatrix   rbi :   Row number of bottom right of query submatrix   rbj :   Column number of bottom right of query submatrix Input: mat[M][N] = {{1 2 3 4 6} {5 3 8 1 2} {4 6 7 5 5} {2 4 8 9 4} }; Query1: tli = 0 tlj = 0 rbi = 1 rbj = 1 Query2: tli = 2 tlj = 2 rbi = 3 rbj = 4 Query3: tli = 1 tlj = 2 rbi = 3 rbj = 3; Output: Query1: 11 // Sum between (0 0) and (1 1) Query2: 38 // Sum between (2 2) and (3 4) Query3: 38 // Sum between (1 2) and (3 3)

순진한 알고리즘:  

우리는 모든 쿼리를 반복하고 넓은 범위의 숫자에 비해 너무 큰 O (q*(N*M)) 최악의 경우에서 각 쿼리를 계산할 수 있습니다.

// Pseudo code of Naive algorithm. Arr[][] = input_matrix For each query: Input tli tlj rbi rbj sum = 0 for i from tli to tbi (inclusive): for j from tlj to rbj(inclusive): sum += Arr[i][j] print(sum) 

최적화된 솔루션: 

합산면적표 이러한 유형의 쿼리를 O(M*N)의 전처리 시간으로 줄일 수 있으며 각 쿼리는 O(1)에서 실행됩니다. 합산 면적 테이블(Summed Area Table)은 그리드의 직사각형 하위 집합에 있는 값의 합을 빠르고 효율적으로 생성하기 위한 데이터 구조 및 알고리즘입니다. 

합산 면적 테이블의 임의 지점(x y)에 있는 값은 (x y)를 포함한 위쪽 및 왼쪽에 있는 모든 값의 합계입니다.

최적화된 솔루션은 아래 게시물에 구현되어 있습니다.

  최적화된 접근방식 구현