BOJ 2042번: 구간 합 구하기

문제

문제 바로가기> BOJ 2042번: 구간 합 구하기

2042번: 구간 합 구하기

 

풀이

indexed tree를 이용해서 푸는 문제다. 

다음과 같이 구간합을 저장하고 있는 트리를 만들 것이다. 

자식 노드의 합 = 부모 노드

 

크게 4가지 단계로 볼 수 있는데, 

 

1. tree의 크기를 설정한다.

    tree의 크기는 N보다 크면서 N과 가장 가까운 2의 거듭제곱으로 설정하는데,

    이는 tree의 depth가 1 증가할수록, 노드의 개수가 2배씩 늘어나는 특징을 반영한 것이다.

 

2. leaf node 들을 채워준다.

    입력으로 받을 수 들은, indexed tree의 leaf node이다.

    이 수들을 [tree_size ~ tree_size+N] 만큼 = leaf node 자리에 채워준다.

 

3. indexed tree를 만들어준다.

    앞서 채워 둔 leaf node들을 이용하여, 부모 node부터 ~> root 까지 값을 채워주며,

    indexed tree를 만들어준다.

    우리는 구간 합을 구하는 게 목표이므로, 부모 node의 값 = left node의 값 + right node의 값이 될 것이다.

 

 

4. 각 연산을 수행하는 함수를 만든다.

   해당 문제에서 요구하는 연산은 값 변경과 구간합 구하기 총 2가지 이다.

   

    update

   먼저 값을 변경부터 살펴보면, 해당 leaf node의 값을 변경한 후,

   점점 위로 올라가면서, 부모 노드들이 이 값을 반영하도록 만들어주면 된다.

   이 때, 주의할 점은, 문제에서 입력으로 주어지는 인덱스와 우리가 tree에서 사용하는 인덱스는 다르다는 점이다.

   tree에 맞는 인덱스로 설정하기 위해서 (tree_size-1) 값을 더해줄 필요가 있다.

   ( 이는 구간합을 구하는 인덱스를 받았을 때도 마찬가지다! )

 

    Interval_sum

    구간합의 경우 해당 범위 내에 포함되는 값을 취하는데,

    tree의 right인 경우에는 left를,

    tree의 left인 경우에는 right 값을 취하고

    각각 위로 이동한다.

    이 부분은 그림을 보고 설명하는 게 쉬울 것 같다. 열심히 만들었다 ^^

    

   아래 그림에서 left는 index=4인 부모 node의 right child이고,

                          right는 index=6인 부모 node의 left child 이다.

   이 경우 두 값을 모두 취해줘야 하는데,

   그 이유는 앞으로 나올 구간 합에 이 두 값은 포함되지 않을 것이기 때문,,

    종료조건인 경우 while문을 빠져 나온다.

    

 

C++

#include<iostream>
#include<vector>
using namespace std;

int N, M, K, tree_size = 1;
vector<long long> tree; //index start with 1

void make_indexed_tree() {
	for (int i = tree_size - 1; i > 0; i--) {
		tree[i] = tree[i << 1] + tree[(i << 1) | 1]; // left node(*2) + right node(*2+1)
	}
}

void update(int idx, long long val) {
	idx += (tree_size - 1); // tree에 알맞는 index로 변환
	tree[idx] = val; // b번째 값을 c로 update
	while ((idx >>= 1) > 0) tree[idx] = tree[idx << 1] + tree[(idx << 1) | 1]; // 조상들도 update
}

long long interval_sum(int left, int right) {
	left += (tree_size - 1); right += (tree_size - 1); // tree에 알맞는 index로 변환

	long long res = 0;
	while (left <= right) {
		if ((left & 1) == 1) res += tree[left]; // tree의 right일 때 값을 취함
		if ((right & 1) == 0) res += tree[right]; // tree의 left일 때 값을 취함
		left = (left + 1) >> 1; // (left+1)/2 node로 이동
		right = (right - 1) >> 1; // (right-1)/2 node로 이동
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("input.txt", "r", stdin); // task /f /PID [pid]

	cin >> N >> M >> K;

	// set tree size
	while (tree_size < N) tree_size <<= 1;
	tree.resize(tree_size << 1);

	// set leaf node
	long long tmp;
	for (int i = tree_size; i < tree_size + N; i++) {
		cin >> tmp; tree[i] = tmp;
	}

	make_indexed_tree();

	long long a, b, c;
	for (int i = 0; i < M + K; i++) { // query
		cin >> a >> b >> c;
		if (a == 1) update(b, c); // b번째 값을 c로 바꿈
		else if (a == 2) cout << interval_sum(b, c) << "\n"; // [b, c] 구간 합 출력
	}
}

 

Java

import java.io.*;
import java.util.*;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	static int N, tree_size=1;
	static long [] tree;
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int M, K;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		// set tree size
		while(tree_size < N) tree_size <<= 1;
		tree = new long[tree_size << 1];
		
		// set leaf node
		for(int i=tree_size; i<tree_size+N; i++) tree[i] = Long.parseLong(br.readLine());
		
		make_indexed_tree();
		
		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) update(b, c);
			else if(a==2) interval_sum(b, (int)c);
		}
 
		System.out.println(sb.toString());
		br.close();
	}

	private static void update(int idx, long val) {
		idx += (tree_size-1);
		tree[idx] = val;
		while((idx>>=1) > 0) tree[idx] = tree[idx<<1] + tree[idx<<1|1];
	}

	private static void interval_sum(int left, int right) {
		left += (tree_size-1);
		right += (tree_size-1);
		
		long res = 0;
		while(left<=right) {
			if((left & 1) == 1) res+=tree[left]; // right에 있으면 취함
			if((right & 1) == 0) res+=tree[right]; // left에 있으면 취함
			left = (left+1) >> 1;
			right = (right-1) >> 1;
		}
		sb.append(res+"\n");
	}

	private static void make_indexed_tree() {
		for(int i=tree_size-1; i>0; i--) {
			tree[i] = tree[i<<1] + tree[i<<1|1]; // left node + right node
		}
	}
}