[백준] 자바 2268 수들의 합 7

문제

N개의 수 A[1], A[2], …, A[N] 이 주어졌을 때, 함수 Sum(i, j)는 A[i] + A[i+1] + … + A[j]를 구하는 함수이다. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 이러한 (i, j)가 여러 개 주어졌을 때도 별로 어려운 문제는 아니다.

Sum함수와 더불어 Modify라는 함수를 정의하자. Modify(i, k)를 수행하면 A[i] = k가 되는 함수이다. Sum함수와 Modify 함수의 사용 목록이 주어졌을 때, 이에 해당하는 연산을 하는 프로그램을 작성하시오. 두 함수를 섞어서 사용할 수도 있다.

입력

첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 나타내며, 0일 경우에는 Sum 함수를, 1일 경우에는 Modify 함수를 나타낸다. 다음 두 수는 각 함수의 인자 (i, j)나 (i, k)를 나타낸다. 처음에는 A[1] = A[2] = … = A[N] = 0이다. Modify인 경우에 1 ≤ k ≤ 100,000 이다.

출력

Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값을 출력한다.

---

테스트 케이스

 

입력 1

3 5
0 1 3
1 1 2
1 2 3
0 2 3
0 1 3

출력 1

0

3

5

 

입력 2

3 3
1 3 5
0 3 2
0 2 3

출력 2

5

5

---

접근

세그먼트 기본 문제인데 약간의 함정?...이 있었네요

보통 i<j일때만 생각하지만 이 문제에서는 j>i도 생각해주어야 합니다.

그것만 빼면 일반적인 세그먼트 트리 문제랑 같습니다.

---

코드

import java.io.*;
import java.util.*;
import java.util.regex.Pattern;

public class Main {

	static long tree[],arr[];
	public static long 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);
	}
	public static long 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];
		if(start == end) 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 long modify(int start, int end, int node, int index, int val) {
		if(index < start || index > end) return tree[node];
		if(start == end) return tree[node] = val;
		int mid = (start+end)/2;
		return tree[node] = modify(start,mid,node*2,index,val) + modify(mid+1,end,node*2+1,index,val);
	}
	public static void main(String[] args) throws Exception {
		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 M = Integer.parseInt(st.nextToken());
		tree = new long[4*N];
		arr = new long[N];
		init(0,N-1,1);
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken())-1;
			if(a==0) {
				if(b<=c)
					bw.append(String.valueOf(sum(0,N-1,1,b,c))+"\n");
				else {
					bw.append(String.valueOf(sum(0,N-1,1,c,b))+"\n");
				}
			}
			else {
				modify(0,N-1,1,b,c+1);
				arr[b]=c+1;
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

---

주의

i<j,   j>i , i==j