백준 11659번: 구간 합 구하기 4 (JAVA)

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

이 문제는 단순 반복문으로 풀면 무조건 시간초과가 난다.
그래서 누적 합을 구하는 알고리즘인 세그먼트 트리를 사용해야한다.

참고 블로그:
https://blog.naver.com/ndb796/221282210534

세그먼트 트리는 트리에 각 구간 별 누적 합을 저장해 놓는 알고리즘 이다.

사진 출처 : https://www.acmicpc.net/blog/view/9

루트 노드에 0~9까지의 누적합을 넣고
구간을 반으로 나누어 왼쪽 오른쪽에 각각 누적합을 넣어간다.
구간 별 누적합을 구할 때는 트리에서 값을 가져오면 된다.

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

public class Main{
	static StringTokenizer st;
	static int N;
	static int tree[];
	static int arr[];
	
	static int init(int start,int end,int node) {
		if(start == end) {
			return tree[node] =arr[start]; 
		}
		
		int mid=(start+end)/2;
		
		return tree[node]=init(start,mid,node*2) + init(mid+1 ,end,node*2+1);
	}
	static int sum(int start,int end,int node, int left, int right) {
		if(left>end || right<start) { //범위를 벗어남
			return 0; 
		}if(left<=start && end<=right) {
			return tree[node];
		}
		int mid=(start+end)/2;
		return sum (start,mid,node *2,left,right)+ sum(mid+1,end,node*2+1,left,right);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st= new StringTokenizer(br.readLine());
		
		N= Integer.parseInt(st.nextToken());
		int M= Integer.parseInt(st.nextToken());
		int a=0,b=0;
		tree= new int[N*4];
		int result;
		arr = new int[N];
		st= new StringTokenizer(br.readLine());
		
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		init(0,N-1,1);
		for(int i=0;i<M;i++) {

			st= new StringTokenizer(br.readLine());
			a= Integer.parseInt(st.nextToken());
			b= Integer.parseInt(st.nextToken());
			
			result = sum(0,N-1,1,a-1,b-1);
			bw.write(String.valueOf(result)+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
		
	}
}

새로운 개념을 배웠다.