BOJ - 1275 ) 커피숍2

 

---

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

1275번: 커피숍2

---

주말에 할게 없어서 세그먼트 트리를 복습하며 문제를 풀었다.. ( 사실할게많은데 안하는것뿐 )

 

세그먼트 트리는 Divide and Conquer를 기반으로 자료를 관리하는 자료구조이다.

 

적절한 Query에 대해서, 그노드가 해당되었는지의 여부를 한판하고 재귀함수를통해 처리해준다.

 

---

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

public class 커피숍2 {
	public static long num[];
	public static long query[][];
	public static long seg[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		num = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) {num[i] = Integer.parseInt(st.nextToken());}
		query = new long[q][4];
		int segsize = (int) Math.pow(2, 1+Math.ceil(Math.log10(n) / Math.log10(2)));
		seg = new long[segsize];
		SegInit(1,0,n-1);
		for(int i = 0 ; i < q ; i++) {
			st = new StringTokenizer(br.readLine());
			int left = Integer.parseInt(st.nextToken())-1;
			int right = Integer.parseInt(st.nextToken())-1;
			if(right < left) {int t = right; right = left ; left =t;}
			long res = Sum(1,0,n-1,left , right);
			sb.append( res + "\n" );
			int idx = Integer.parseInt(st.nextToken())-1;
			int change = Integer.parseInt(st.nextToken());
			long diff = change - num[idx];
			num[idx] = change;
			Update(1,0,n-1,idx ,diff);
		} // end method
		System.out.println(sb);
	}
	private static long SegInit(int node, int start, int end) {
		if(start == end) {
			return seg[node] = num[start];
		} else {
			int mid = (start + end)>>1;
			return seg[node] = SegInit(2*node , start , mid) + SegInit(2*node+1, mid+1, end);
		}
	}
	private static void Update(int node , int start , int end ,int Target, long diff) {
		if(start > Target || Target > end) return ;
		seg[node] += diff;
		if(start != end) {
			int mid = (start + end ) >>1;
			Update(node*2 , start , mid , Target ,diff );
			Update(node*2+1 , mid+1 , end , Target ,diff );
		}
	}
	private static long Sum(int node , int start , int end ,int left, int right) {
		if(right < start || left > end ) return 0;
		if(left <= start && end <= right) {return seg[node];}
		int mid = (start + end )>>1;
		return Sum(2*node, start , mid , left ,right) + Sum(2*node+1, mid+1 , end , left ,right);
	}
}

---