BOJ 11658(구간 합 구하기 3) 문제 풀이

목차

• 참조
• 개요
  • 시간복잡도: $ O(N^2 + M \log^2 N) $
  • 공간복잡도: $ O(N^2) $
• 문제 풀이
• 구현

참조

개요

시간복잡도: $ O(N^2 + M \log^2 N) $

공간복잡도: $ O(N^2) $

• N은 원소의 수, M은 연산의 수이다.

문제 풀이

이 문제도 역시 인덱스 트리라고 부르는 자료구조를 써도 풀리긴 하지만, 펜윅 트리가 굉장히 간단하기 때문에 이것으로 문제를 풀었다.

원소가 하나씩 업데이트될 때, 구간의 합을 구하라는 문제는 그냥 펜윅 트리를 쓰라는 문제이다. 왜냐하면 BIT가 그에 최적화되어 있기 때문이다.

이 문제는 구간 합 구하기와는 달리 2차원이기 때문에, data 배열도 2차원으로 잡아야 한다. 즉, data[][] 형식이 될 것이다.

구간 합을 구하는 것은 1차원을 2차원으로 확장한 것에 불과하다.

• 1차원은 sum(a,b) = sum(b) - sum(a-1)이었다.
• 2차원은 sum(x1~x2, y1~y2) = sum(x2, y2) - sum(x1-1, y2) -sum(x2, y1-1) + sum(x1-1, y1-1)이다.
  • 손으로 그림을 딱 한번만 그려보면 위 식이 단번에 이해될 것이다.

업데이트 연산 역시 2차원으로 확장한 것에 불과하다.

구현

이 문제는 2차원이기 때문에 sum과 update에서 중첩 while문을 볼 수 있을 것이다.
그리고 BOJ 02042(구간 합 구하기) 문제 풀이와는 달리 arr 배열을 만들지 않고 풀이를 적었다.

#include "../library/sharifa_header.h"
#include "../library/fenwick_tree_2D_BIT.h"

int N, m;

int main_11658() {
	ios::sync_with_stdio(false);    cin.tie(NULL);

	cin >> N >> m;

    FenwickTree2D BIT(N);

    int w, x1, y1, x2, y2, val;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> val;
			BIT.update(i, j, val);
		}
	}
	while(m--){
        cin >> w >> x1 >> y1;
		if (w){
            cin >> x2 >> y2;
			cout << BIT.sum(x1, y1, x2, y2) << '\n';
        } else {
            cin >> val;
			BIT.update(x1, y1, val);
		}
	}
	return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?