문제

백준 11659 구간 합 구하기 4 문제 보러가기



해설

카카오 인턴십 코딩테스트에서 풀지 못한 문제가 세그먼트 트리를 사용하면 풀린다는 글을 보고 세그먼트 트리에 대해 공부해보았다. 백준 사이트에 분류되어있는 문제를 하나씩 풀어보는 단계에 있으며 해당 문제는 가장 기초가 될 수 있는 문제다.

그리고 두 가지 방법으로 풀었는데 세그먼트 트리를 공부하려면 첫번째 코드로 푸는 것이 좋고 효율성을 생각한다면 두번째 코드가 좋았다.



풀이

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

public class Main {
	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 M = Integer.parseInt(st.nextToken());
		int h = (int) Math.ceil(Math.log(N) / Math.log(2));
		int size = (int) Math.pow(2, h + 1);

		int[] nums = new int[N + 1];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 1; i <= N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		int[] tree = new int[size];

		tree[1] = init(nums, tree, 1, 1, N);

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int left = Integer.parseInt(st.nextToken());
			int right = Integer.parseInt(st.nextToken());

			if (left == right)
				System.out.println(nums[left]);

			else
				System.out.println(sum(tree, 1, 1, N, left, right));
		}
	}

	public static int sum(int[] tree, int node, int start, int end, int left, int right) {
		if (left > end || right < start)
			return 0;

		if (left <= start && right >= end)
			return tree[node];

		int mid = (start + end) / 2;
		return sum(tree, node * 2, start, mid, left, right) + sum(tree, node * 2 + 1, mid + 1, end, left, right);
	}

	public static int init(int[] nums, int[] tree, int node, int start, int end) {
		if (start == end) { // 자식이 없는 리프노드
			return tree[node] = nums[start];
		}

		int mid = (start + end) / 2;

		return tree[node] = init(nums, tree, node * 2, start, mid) + init(nums, tree, node * 2 + 1, mid + 1, end);
	}
}

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

public class Main {
    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 M = Integer.parseInt(st.nextToken());
        
        int[] S = new int[N+1];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i <= N; i++){
            S[i] = Integer.parseInt(st.nextToken());
            S[i] += S[i-1];
        }
        
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            System.out.println(S[end] - S[start - 1]);
        }
    }
}