개요

백준 12837번: 가계부 (Hard)

• 입력
  첫째 줄에 월곡이가 살아온 날 N, 쿼리의 개수 Q가 주어진다. (N ≤ 106, Q ≤ 105)

  둘째 줄부터 Q+1번째 줄까지는 아래와 같은 형식의 쿼리가 주어진다.

  1 p x : 생후 p일에 x를 추가한다. (1 ≤ p ≤ N, -2×109 ≤ x ≤ 2×109)
  2 p q : 생후 p일부터 q일까지 변화한 양을 출력한다. (1 ≤ p ≤ q ≤ N)

• 출력
  각 2 쿼리에 대해 계산된 값을 각 줄에 출력한다.

접근 방식

1. 기본적인 방법으론 배열이나 벡터같은 컨테이너에 저장한 후,
   각 쿼리마다 값들을 변경하고, 일일이 변화량을 계산하는 방법이 있다.

2. 문제는 쿼리 갯수가 최댓값이 10만개, 숫자 갯수가 100만개이므로,
   10만개의 쿼리가 똑같이 100만개의 변화량을 계산하라고 하면
   시간초과가 난다.
   따라서 세그먼트 트리를 사용하여 구현을 하였다.

3. 숫자의 갯수가 최대 100만개이고 2^20>100만이므로
   트리의 크기를 2^21로 잡았다.

   //2^20이 1048576
   long long segTree[2'097'152];

   또한 숫자 최댓값이 2*10^9으로 int값을 안 넘긴 하지만
   두 수를 더할때 넘어가므로 int보다 큰 자료형을 사용하여야 한다.

4. 처음에 N과 Q를 입력받은 다음

   void Input() {
   	int a=0, b=0, c=0;
   	cin >> N >> Q;
   	while (firstLeafNodeIdx < N) {
   		firstLeafNodeIdx *= 2;
   	}
   	for (int i = 0; i < Q; i++) {
   		cin >> a >> b >> c;
   		if (a == 1) {
   			ReadjustTree(b - 1, c );
   		}
   		else {
   			PrintAnswer(b - 1, c - 1);
   		}
   	}
   
   }

   firstLeafNodeIdx값을 2를 계속 곱해주는 과정을 통해
   첫 리프노드 인덱스를 구해준다.

   그 후 Q개의 쿼리를 받으며 a=1일때 readjustTree()함수를 사용하고,
   a=2일때 printAnswer()함수를 사용한다.
   

5. ReadjustTree( int b, int c )함수는 firstLeafNodeIdx+b 인덱스의 값을 c만큼 변경 후, 해당 노드의 부모 노드들도 다 c만큼 변경하는 함수이다.

   void ReadjustTree(int b, int c) {
   	int tmp = firstLeafNodeIdx + b;
   	while (tmp > 0) {
   		//구간합같은 문제는 값이 다른값으로 변경되서 변화량을 더해야 함.
   		//이문제는 수입과 지출이 추가되는 형태로 c값을 그냥 더해도 무방
   		segTree[tmp] += c;
   		tmp /= 2;
   	}
   }

   이런식으로 변경될 때 루트노드부터 firstLeafNodeIdx-1번째 노드까지 다 변경하지 않고 부모노드들만 갱신해준다면
   트리의 최대 높이가 21이므로 최대 21번만 연산하면 되어서 빠르다.

6. FindChanges(int targetL, int targetR, int nodeNum, int curL, int curR)함수는
   탐색 범위인 [curL, curR]에 목표 범위인 [targetL,targetR]가
   포함되어있는지 체크한다.
   포함한다면 해당 범위의 값을 바로 return하고,
   목표범위를 벗어나면 바로 return하는 구조로 짜여있다.

   long long FindChanges(int targetL, int targetR, int nodeNum, int curL, int curR) {
   	if (targetR < curL || curR < targetL) return 0;
   	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
   	int mid = (curL + curR) / 2;
   	return FindChanges(targetL, targetR, nodeNum * 2, curL, mid) + FindChanges(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
   }

전체 코드

#include<iostream>


using namespace std;

//2^20이 1048576
long long segTree[2'097'152];

int N,Q, firstLeafNodeIdx=1;

void ReadjustTree(int b, int c) {
	int tmp = firstLeafNodeIdx + b;
	while (tmp > 0) {
		//구간합같은 문제는 값이 다른값으로 변경되서 변화량을 더해야 함.
		//이문제는 수입과 지출이 추가되는 형태로 c값을 그냥 더해도 무방
		segTree[tmp] += c;
		tmp /= 2;
	}
}

long long FindChanges(int targetL, int targetR, int nodeNum, int curL, int curR) {
	if (targetR < curL || curR < targetL) return 0;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
	int mid = (curL + curR) / 2;
	return FindChanges(targetL, targetR, nodeNum * 2, curL, mid) + FindChanges(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
}

void PrintAnswer(int b, int c) {
	cout << FindChanges(b, c, 1, 0, firstLeafNodeIdx - 1)<<'\n';
}

void Input() {
	int a=0, b=0, c=0;
	cin >> N >> Q;
	while (firstLeafNodeIdx < N) {
		firstLeafNodeIdx *= 2;
	}
	for (int i = 0; i < Q; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			ReadjustTree(b - 1, c );
		}
		else {
			PrintAnswer(b - 1, c - 1);
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

입력값으로 인해 ReadjustTree함수에서 리프노드가 변경되면
부모노드를 변경값으로 갱신해줘야하는 부분에서 고민을 했었다.

기본 구간합 문제같은 경우는 값을 다른 값으로 변경을 하므로
두 값의 차이값만큼만 부모노드들에 갱신해주면 되었지만,
이 문제는 수입,지출 문제이므로 애초에 변화량이 입력값으로
해당 값을 그대로 더해주면 된다.