공부공간

BOJ - 2042 ) 구간 합 구하기 본문

알고리즘/SegmentTree

BOJ - 2042 ) 구간 합 구하기

개발자가될수있을까? 2020. 3. 17. 17:25


 

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

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 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번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의

www.acmicpc.net


연속 합을 구하는 문제에서 Segment Tree 와 Fenwick Tree를 자주 사용하는데, 

 

Segment Tree로 위 문제를 풀어보았다. 사실상 그냥 배열로 구현하였다..

 

문제에서 index번째의 값을 바꾸는 쿼리가 등장하기 때문에

 

구간을 계산하여서 index 번째를 포함하는 누적합은 값을 적절하게 더해주어서 조정을 해주어야한다.

 

구간합은 Seg배열에 저장되어있으므로 재귀함수를 통해서 구간을 찾아가야한다.

 




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

public class Main {
	static long seg[] ,num[];
	public static void main(String[] args) throws Exception {
		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 k = Integer.parseInt(st.nextToken());
		num = new long[n];
		seg = new long[4*n];
		for(int index = 0 ; index < n ; index++) {num[index] = Integer.parseInt(br.readLine());}
		seginit(1,0,n-1);
		for(int index = 0 ; index < m + k ; index++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			if(a ==1) {
				// update
				int i = b-1;
				long diff = c - num[i];
				num[i] = c;
				update(1,0,n-1,i,diff);
			}
			else {
				// compute sum
				if(b > c) {
					int temp = b;
					b = c;
					c= temp;
				}
				System.out.println(sum(1,0,n-1,b-1,c-1));
			}
			
		}
	}
	private static void update(int n, int s, int e, int i, long diff) {
		if(i < s || i > e) return;
		seg[n] +=diff;
		if(s!=e) {
			update(n*2 , s , (s+e)/2 , i , diff);
			update(n*2+1 , (s+e)/2+1,e , i , diff);
		}
	}
	private static long sum(int n, int s, int e, int l, int r) {
		if( l > e || r < s) return 0;
		else if(l <= s && e <= r) return seg[n];
		else {
			return sum(2*n , s , (s+e)/2 , l , r) +sum(2*n+1 , (s+e)/2+1,e,l,r);
		}
	}
	public static long seginit(int n , int s , int e) {
		if(s == e) {
			// leaf node
			return seg[n] = (long )num[s];
		}
		else {
			return seg[n] = seginit(n*2 , s , (s+e)/2) + seginit(n*2+1, (s+e)/2+1, e);
		}
	}

}

'알고리즘 > SegmentTree' 카테고리의 다른 글

BOJ - 6549 ) 히스토그램에서 가장 큰 직사각형  (0) 2020.10.28
BOJ -2268 ) 수들의 합  (0) 2020.05.17
BOJ - 10868 ) 최솟값  (0) 2020.05.16
BOJ - 2357 ) 최솟값과 최댓값  (0) 2020.05.16
BOJ - 1275 ) 커피숍2  (0) 2020.05.16
Comments