쌉쌀한 무화과의 개발로그

[문제]

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

[입력]

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

[출력]

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

[예제]

>문제 풀이

인덱스 트리를 이용하여 풀었습니다.

처음 접하는 알고리즘으로 푸느라 사실 아직 이해를 제대로 했는지 모르겠습니다.

응용 문제가 많다고 하니 개념을 좀 더 살펴 본 후 관련 문제들을 더 풀어보면 좋을 것 같습니다.

​

인덱스 트리는 구간합을 구해야할 때, 중간에 인덱스의 값이 변하는 상황에서 쓰입니다.

배열로도 구간합을 저장할 수 있지만, 이 경우 특정 인덱스에 담긴 값을 바꿀 경우 배열 전체를 갈아엎어야 합니다..

​

그래서 이런 경우는 인덱스 트리를 사용하면 되는데, 포화 이진트리의 리프노드에 배열로 받은 값을 넣고 그 위로 구간합을 구하면서 올리는 구조입니다.

처음에 트리를 만들기 위해서는 Bottom-up으로 리프노드부터 위로 올라가는 방법을 쓰는데, 이후 query와(구간합 구하는 메소드) update에서는(특정 인덱스에 담긴 값을 변경) Top-down과 Bottom-up 2가지 방식으로 구현할 수 있습니다.

(알고리즘 수업에서 두 가지 방법으로 모두 구현해 보았지만, 이 문제에서는 top-down으로 제출하였습니다.)

​

**구현

1. N개의 배열값을 받았다면, 이제 인덱스 트리에 저장해야합니다.

인덱스 트리의 노드 개수는 2의 제곱수-1개 이고 리프 노드에 N개의 값을 저장해야 합니다.

근데 노드 번호는 0부터 시작하는데 연산을 0부터 하도록 구현하기 너무 번거롭습니다. 그래서 node[0]은 남겨두고 1부터 2N까지가 우리가 실제 값을 넣고 사용하는 노드입니다. 즉 트리의 인덱스 N~2N-1까지가 리프노드이고, 여기에 nums[N]을 담아야합니다.

​

=> N보다 크거나 같은 2의 제곱수가 리프노드의 개수 S이고, 2*S가 트리의 노드 개수 입니다.

ex) N=5 이면 S= 8(=2^3)

​

2. query ( left, right, node, queryLeft, queryRight)

left: 리프노드의 첫번째 인덱스(=1)

right: 리프노드의 마지막 인덱스(=S)

node: 현재 노드의 번호(Top-down으로 구현했으니 처음에 1로 넘긴다.)

queryLeft: 구하고자하는 구간의 왼쪽 인덱스

queryRight: 구하고자하는 구간의 오른쪽 인덱스

​

분기점을 3개로 나눠서 구현한다.

(1) (left, right): 현재노드가 담고있는 구간합의 구간과 (queryLeft, queryRight)와 범위가 겹치지 않는 경우

(2) (left, right)와 (queryLeft, queryRight)와 딱 맞는 경우

(3) (left, right)와 (queryLeft, queryRight)이 걸쳐있는 경우

:자식 노드들로 내려가서 필요한 값만 올릴 수 있도록 해야함.

: return query(왼쪽부분) + query(오른쪽 부분)

​

3. update(left, right, node, target, diff)

: 타겟을 찾아가며 타겟을 포함하는 구간합을 담은 노드에 +diff 처리를 해준다.

: diff 은 c - nums[target]

(c는 업데이트 해야할 값 , nums[target]은 업데이트 전의 값)

>전체 코드

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


public class Main {
	static long nums[], tree[];
	static int N, M, K, S;
	
	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());
		M= Integer.parseInt(st.nextToken());
		K= Integer.parseInt(st.nextToken());
		nums= new long[N];
		
		for(int i=0; i<N; i++) {
			nums[i]= Long.parseLong(br.readLine());
		}
		
		S=1;
		while(S<N) {
			S*=2;
		}
		tree= new long[S*2];
		
		initBU();
		
		int a, b;
		long c;
		for(int i=0; i<M+K; i++) {
			st= new StringTokenizer(br.readLine());
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			c= Long.parseLong(st.nextToken());
			
			if(a==1) { //1이면 업뎃
				update(1, S, 1, b, c-nums[b-1]);
				nums[b-1]=c;
			}else if(a==2) { //2면 구간합
				System.out.println(query(1, S, 1, b, c));
			}
		}
		
	}//main
	
	static void initBU() {
		//Leaf에 값 반영
		for(int i=0; i<N; i++) {
			tree[S+i]=nums[i];
		}
		//내부노드 채움
		for(int i=S-1; i>0; i--) {
			tree[i]= tree[i*2]+tree[i*2+1];
		}
	}//init
	
	static long query(int left, int right, int node, int queryLeft, long queryRight) {
		// 연관이 없음
		if(right<queryLeft||queryRight<left) {
			return 0;
		}
		// 현재 노드가 쿼리 범위에 포함됨
		else if(queryLeft<=left&&right<=queryRight) {
			return tree[node];
		}
		// 현재 노드가(정확히는 구간이) 쿼리 범위에 포함은 안되는데, 겹침
		else {
			int mid= (left+right)/2;
			long leftResult= query(left, mid, node*2, queryLeft, queryRight);
			long rightResult= query(mid+1, right, node*2+1, queryLeft, queryRight);
			return leftResult+rightResult;
		}
	}//query
	
	static void update(int left, int right, int node, int target, long diff) {
		//연관없음
		if(target<left||right<target) return;
		//연관 있음
		tree[node]+=diff;
		if(left!=right) {
			int mid= (left+right)/2;
			update(left, mid, node*2, target, diff);
			update(mid+1, right, node*2+1, target, diff);
		}
	}//update
}