[BOJ] 백준 12837번 가계부(Hard) (Java) - 펜웍 트리

#12837 가계부 (Hard)

난이도 : 골드 1

유형 : 세그먼트 트리 / 펜웍 트리 

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위치에 x를 추가하여 트리를 업데이트 시켜주면 되고, 2번 쿼리는 p~q구간의 합을 구해주면 된다. 펜윅 트리의 구간합은 sum[q] - sum[p-1]로 구할 수 있다.

 

3일에 10000 추가하기 (1 3 10000)

• 3일에 10000을 추가하면, 3, 4, 8모두 업데이트 된다

3일에 10000 추가하기 (1 3 10000)

 

4일에 -5000 추가하기 (1 4 -5000)

• 4일에 -5000을 추가하면, 4, 8 모두 업데이트 된다. 

4일에 -5000 추가하기 (1 4 -5000)

 

7일에 -3000 추가하기 (1 7 -3000)

• 7일에 -3000을 추가하면, 7, 8 모두 업데이트 된다. 

7일에 -3000 추가하기 (1 7 -3000)

 

1일 ~ 10일 구간합 (2 1 10)

• 1일부터 10일까지 구간 합을 구하면 sum(10) - sum(0)이므로 2,000이 출력된다.
• 10일까지의 합은 tree[10] + tree[8]이고, sum(0) = 0이다.

 

1일 ~ 10일 구간합 (2 1 10)

 

이런식으로 계속해서 쿼리를 풀어나가면 된다.

 

풀이 코드  - 펜윅 트리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static long[] tree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		tree = new long[n+1];
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<q; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(op == 1) {
				update(a,b);
			} else {
				sb.append(sum(b)- sum(a-1)+"\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static void update(int idx, int val) {
		while(idx <= n) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}
	
	static long sum(int idx) {
		long result = 0;
		while(idx > 0) {
			result += tree[idx];
			idx -= (idx & -idx);
		}
		return result;
	}	
}

 

 

풀이 코드  - 세그먼트 트리

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static long[] arr, tree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		arr = new long[n+1];
		tree = new long[n*4];
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<q; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(op == 1) {
				arr[a] += b;
				update(1, n, 1, a);
			} else {
				sb.append(pSum(1,n,1,a,b)+"\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static long update(int s, int e, int node, int idx) {
		if(idx < s || e < idx) return tree[node];
		if(s == e) {
			return tree[node] = arr[idx];
		}
		int mid = (s+e)/2;
		return tree[node] = update(s, mid, node*2, idx) + update(mid+1, e, node*2+1, idx);
	}
	
	static long pSum(int s, int e, int node, int l, int r) {
		if(r < s || e < l) return 0;
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		return pSum(s, mid, node*2, l, r) + pSum(mid+1, e, node*2+1, l, r);
	}
}