백준 2042번 <구간 합 구하기>

백준 알고리즘 2042번

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

---

2042번

어떤 N개의 수가 주어졌을 때, 구간 합을 구하여라.

 

입력으로 첫 줄에 숫자의 개수 N, 수의 변경이 일어나는 횟수 M, 구간 합을 구하는 횟수 K가 주어진다.

그 다음 N개의 줄에 걸쳐 숫자가 주어진다.

그 다음 M+K개의 줄에 걸쳐 a, b, c가 주어진다.  a가 1이면 수의 변경을 해야 하고 b번째 값을 c로 바꾼다. a가 2이면 구간 합을 구하며 b부터 c까지의 구간 합을 구해서 출력한다.

 

출력은 구간 합의 연산의 횟수인 K줄이 출력되며, 각 연산에 맞는 구간 합을 출력한다.

---

문제 해결

처음에 이 문제를 그냥 풀려고 했는데 절대 안풀린다!

그래서 구글링을 해보니 세그먼트 트리를 사용하여 해결해야 한다고 했다.

 

세그먼트 트리는 새로운 자료구조여서 열심히 공부했다!

 

2022.04.19 - [그냥 공부] - [알고리즘] 세그먼트 트리

 

세그먼트 트리를 이용하여 풀면 바로 풀 수 있다.

이때 조심해야 할 것은 세그먼트 트리에서 데이터 배열의 index는 0부터 시작인데 여기서 데이터 배열의 index는 1부터 시작이라는 것이다. 따라서 세그먼트 트리의 함수 중 sum 함수의 left, right와 update 함수의 idx에 -1을 해줘야 한다. 

또한 데이터의 값이 -2^63, 2^63이기 때문에 long 자료형을 써야 한다. (N, M, K는 10,000과 같거나 작기 때문에 int 자료형을 써도 된다.)

---

코드

package bj2042;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input =br.readLine();
		String[] inArr = input.split(" ");
		int N = Integer.parseInt(inArr[0]);
		int op = Integer.parseInt(inArr[1]) + Integer.parseInt(inArr[2]);
		long[] num = new long[N];
		for(int i = 0; i < N; i++) {
			input = br.readLine();
			num[i] = Long.parseLong(input);
		}
		SegmentTree st = new SegmentTree(N, num);
		for(int i = 0; i < op; i++) {
			input = br.readLine();
			inArr = input.split(" ");
			int opCode = Integer.parseInt(inArr[0]);
			if(opCode == 1) {	//update
				int idx = Integer.parseInt(inArr[1]);
				long value = Long.parseLong(inArr[2]);
				long old = st.getNumValue(idx-1);
				st.setNumValue(idx-1, value);
				st.update(0, N-1, 1, idx-1, value - old);
				
			}else if(opCode == 2) {		//sum
				int left = Integer.parseInt(inArr[1]);
				int right = Integer.parseInt(inArr[2]);
				System.out.println(st.sum(0, N-1, 1, left-1, right-1));
			}
		}
	}

}
class SegmentTree {
	long[] num, tree;
	public SegmentTree(int N, long[] n) {
		this.tree = new long[N*4];
		this.num = n;
		init(0, N-1, 1);
	}
	public long init(int start, int end, int nodeN) {
		if(start == end) {
			return this.tree[nodeN] = this.num[start];
		}
		int mid = (start + end) / 2;
		return this.tree[nodeN] = init(start, mid, nodeN*2) + init(mid+1, end, nodeN*2 + 1);
	}
	public long sum(int start, int end, int nodeN, int left, int right) {
		if(left > end || right < start) return 0;
		if(left <= start && end <= right)return this.tree[nodeN];
		int mid = (start + end) / 2;
		return sum(start, mid, nodeN *2, left, right) + sum(mid+1, end, nodeN*2+1, left, right);
	}
	public void update(int start, int end, int nodeN, int idx, long diff) {
		if(idx < start || idx > end) return;
		this.tree[nodeN] += diff;
		if(start == end) return;
		int mid = (start + end) / 2;
		update(start, mid, nodeN*2, idx, diff);
		update(mid+1, end, nodeN*2+1, idx, diff);
	}
	public long getNumValue(int idx) {
		return this.num[idx];
	}
	public void setNumValue(int idx, long value) {
		this.num[idx] = value;
	}

}

---

결과

---