BOJ - 2042 ) 구간 합 구하기

---

 

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

2042번: 구간 합 구하기

---

연속 합을 구하는 문제에서 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);
		}
	}

}

---