2차원 배열의 누적합을 배열을 생성하는 시간복잡도 O(n**2)

기본 아이디어

스크린샷 2022-03-26 오후 11.43.45.png

전체 내모에서 연한내모 구역을 뺀후 이중으로 빠진 진한 네모를더해주면 파란내모의 구간합을 구할수 있다

3*3 배열 누적합 구성

  1. 원본 배열
1 2 3
4 5 6
7 8 9
  1. 편의를 위해 n+1 곱 n+1의 배열을 구성하는게 좋음
0 0 0 0
0 1 3 6
0 5 12 21
0 12 27 45

공식 prefixSum[i][j]=board[i-1][j-1]+prefixSum[i][j-1]+prefixSum[i-1][j]-prefixSum[i-1][j-1]