백준 1275 : 커피숍2

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

1275번: 커피숍2

[ 문제풀이 ]

전형적인 세그먼트 트리를 이용해서 구간합을 구하는 문제이다. 세그먼트 자료구조를 공부하였다면 쉽게 해결할 수 있다.

세그먼트 트리 자료구조를 모르거나 공부하고 싶다면 아래 글을 참고하길 바란다.

https://sorjfkrh5078.tistory.com/14?category=1007493

세그먼트 트리(Segment Tree)

 

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

public class Main {
	
	static class SegTree {
		
		long[] tree;
		
		public SegTree(int N) {
			tree = new long[N << 2];
		}
		
		public long update(int idx, int node, int l, int r, int v) {
			if (l > idx || r < idx) return tree[node];
			if (l == r) return tree[node] = v;
			int mid = (l + r) >> 1;
			return tree[node] = update(idx, node * 2, l, mid, v)
					+ update(idx, node * 2 + 1, mid + 1, r, v);
		}
		
		public long query(int l, int r, int node, int nl, int nr) {
			if (nr < l || nl > r) return 0;
			if (nl <= l && r <= nr) return tree[node];
			int mid = (l + r) >> 1;
			return query(l, mid, node * 2, nl, nr)
					+ query(mid + 1, r, node * 2 + 1, nl, nr);
		}
	}
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int Q = Integer.parseInt(st.nextToken());
			SegTree segTree = new SegTree(N);
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; ++i) {
				int v = Integer.parseInt(st.nextToken());
				segTree.update(i, 1, 1, N, v);
			}
			
			for (int i = 0; i < Q; ++i) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				if (x > y) {
					int temp = y;
					y = x;
					x = temp;
				}
				bw.write(segTree.query(1, N, 1, x, y) + "\n");
				segTree.update(a, 1, 1, N, b);
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}