부분합 알고리즘

 

부분합은 특정 구간의 합을 효율적으로 계산하기 위해 누적합을 활용하는 방법이다.

 

입력할때 전부 더해두고 이후에 재사용한다는 계념이다.

 

그래서 최소 한번이상 사용해야 이득이다.

 

 

 

 

1차원배열은 

 

 index = [1]   [2]    [3]   [4]    [5]      [6] 이 있다

 DP =    [1]   [3]    [6]   [10]   [15]   [21] 배열을 만들어준뒤

 

배열은 이전값에서 M을 더한 값   [N]= [N-1] + M

 

 

3번부터5번값 을 구해야 한다면?

 

아래처럼 3 부터 5까지 index를 하나씩 올리며 구해도 괜찮다. 

 [1]   [2]   [3]   [4]    [5]      [6]

 1      2     3     4      5        6

                3      4     5

                       12

 

 

DP 배열 에서 구하는법은 아래와 같다

 

우선 쉽게 위치로 보자면  

1       3       6 10 15       21

1       2       3~~~5`

 

 

포함되어있지않은 x-1 를 찾아준다

            [3]     [6]     [15]
          [x-1]              [ y]

 

비포함인부분을 포함되어있는 부분에서 빼주면 

            [y]  -  [x-1] 

           15  - 3    =   12

 

 

 

 

 

2차원행렬은 

 

기본적인 아이디어가 똑같기에 더해준뒤 중복값 제거 

 

그렇다면 x1,y1   x2, y2 를 계산할땐 어떤식으로 계산해야할까

 

위와 같은 행렬 에서 해당파란  0,0   1,1  부분을 구하고싶다면

그냥 1,1 부분을 출력해도 무방할것이다.

 

그렇다면

같은 부분을 구하려면 어떻게 해야할까

 

이것도 1차원 행렬 과 같은방식이다.

 

아래는 DP 행열이다

우선 전체 합인 22  

그리고 제외할부분인 6 과 6 을 빼준다

 

그러면 6에는공통적으로 들어가게 되는 1이 두번 빠지게 된다.

그럼으로 공통적으로 빠지는 1을 더해주면  구역값이 나오게 된다.

22 - 6 - 6 +1

이걸 펼쳐본다면

 

전체 크기에 빠진크기만큼 세로 가로를 빼준뒤 중복되어있는부분을 다시 더해주면 완성!

 

행렬  옆 0 줄이 있는건 계산을 쉽게 하기 위해서다.

 

아래 구현 코드와 계산기로 쉽게 확인해보자

 

 

 

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);


	int N, M;
	cin >> N >> M;
	int mix_n = N, mix_m = N;
	vector<vector<int>> vmap(mix_n + 1, vector<int>(mix_m + 1, 0));
	for (int i = 1; i < mix_n + 1; i++)
	{
		for (int j = 1; j < mix_m + 1; j++)
		{
			int k = 0;
			cin >> k;
			vmap[i][j] = k + vmap[i - 1][j] + vmap[i][j - 1] - vmap[i - 1][j - 1];
		}
	}
	for (int i = 0; i < M; i++) {
		int Lx, Ly, Rx, Ry;
		cin >> Lx >> Ly >> Rx >> Ry;
		int mixAnswer = vmap[Lx - 1][Ly - 1] + vmap[Rx][Ry] - vmap[Rx ][Ly - 1] - vmap[Lx - 1][Ry ];
		cout << mixAnswer<<"\n";
	}

 

2D 배열 구간 합 계산기

원본 배열

누적합 배열

Left X (Lx):

Left Y (Ly):

Right X (Rx):

Right Y (Ry):

선택 영역의 합: 0

계산 방법:

선택한 영역의 합 = prefixSum[Rx][Ry] - prefixSum[Rx][Ly-1] - prefixSum[Lx-1][Ry] + prefixSum[Lx-1][Ly-1]

계산에 사용되는 위치:

• 1 prefixSum[Rx][Ry]
• 2 prefixSum[Rx][Ly-1]
• 3 prefixSum[Lx-1][Ry]
• 4 prefixSum[Lx-1][Ly-1]