[백준] 12837. 가계부 (Hard)

문제

살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 했지만, 월곡이는 굉장히 오래 살았기에 원하는 정보를 얻기에는 동작 속도가 너무나도 느렸다. 가끔 입력을 빼먹은 것이 생기면 다시 추가하고 계산하는 것도 느려서, 성격이 급한 월곡이는 결국 스마트폰을 부숴버리고 말았다. 월곡이를 도와주는 프로그램을 작성하기 위해, 아래와 같은 동작들을 처리하는 프로그램을 작성하시오.

작성될 가계부 프로그램은 두 가지 동작을 처리해야 한다. 첫 번째는 월곡이의 생후 p일에 수입/지출 내용을 추가하는 것이다. 수입은 양수, 지출은 음수의 형태로 입력이 들어온다. 두 번째는 월곡이의 생후 p일부터 q일까지 잔고가 변화한 값을 구하고 출력하는 것이다. 월곡이가 빚을 지고 있을 수도 있기에 어떤 i에 대해서 생후 i일의 잔고는 음수일 수 있다.

입력

첫째 줄에 월곡이가 살아온 날 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 세그먼트 트리 문제입니다.

p~q일까지 부분합을 입력받으면서 업데이트해야합니다.

	#include<bits/stdc++.h>

	using namespace std;
	typedef long long ll;
	
	ll sum[4 * 1000001];

	ll inits(ll left,ll right,ll node) {
		if (left == right) {
			return sum[node] = arr[left];
		}
		ll mid = (left + right) / 2;
		return sum[node] = inits(left,mid,node*2) + inits(mid+1,right,node*2+1);
	}

	void update(ll left, ll right, ll node,ll target, ll dif) {
		if (target < left || right < target)
			return;
		sum[node] += dif;
		if (left == right)return;
		ll mid = (left + right) / 2;
		update(left, mid, node * 2, target, dif);
		update(mid + 1, right, node * 2 + 1, target, dif);
		return;
	}

	ll cal(ll left, ll right, ll from, ll to,ll node) { //left right는 분할되는범위   from to는 더해야할 범위	
		if (right<from || to<left) { //범위 밖일경우
			return 0;
		}
		if (from<=left && right<=to ){ //범위 안인경우
			return sum[node];
		}
		ll mid = (left + right) / 2;
		return cal(left, mid, from, to,node*2) + cal(mid + 1, right, from, to,node*2+1);
	}
	int main() {
		ios::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);
		memset(sum, 0, sizeof(sum) * 4);
		ll n, query, p, x, c, q;
		cin >> n >> query;
		
		for (ll i = 0; i < query; i++) {
			cin >> c;
			if (c == 1) {
				cin >> p >> x; //생후 p일에 x를 추가한다
				update(0, n - 1, 1, p - 1, x);
			}
			else if (c == 2) { 
				
				cin >> p >> q;   //생후 p일부터 q일까지 변화한 양을 출력한다.
				cout<<cal(0,n-1,p-1,q-1,1)<<"\n";  //ll cal(ll left, ll right, ll from, ll to,ll node)
			}
		}
	}

세그먼트트리는 선형적으로 합을 구할때(O(N))보다 빠르게 답을 구할 수 있습니다 (O(logN)).

인덱스가 1부터 시작한다는점을 잊어선 안됩니다. 왼쪽 자식노드로 갈때 2*index, 오른쪽 자식노드로 갈때 2*index+1로 편하기때문입니다.

 

기본적인 논리구조는 update와 cal(부분합구하기)가 같습니다.

업데이트나 합을 수행해야하는 범위 [from,to]안에 한 노드의 자식범위 [left,right]가 포함되면 그 노드에 연산을 수행합니다.

그 범위에 포함되지않으면 연산을 수행하지 않거나 0을 반환합니다.