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();
}
}
새로운 개념을 배웠다.