구간 합 구하기 백준 2042

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 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(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

예제 입력 1 

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

예제 출력 1 

17
12

 

풀이방법

첫째 줄

수의 갯수 N( 1<= N <=1000000)

수의 변경이 일어나는 횟수 M (1 <= M <= 10000)

구간의 합을 구하는 횟수 K (1 <= K <= 10000)

 

둘째 줄 ~ N+1번째 줄까지 N개의 수

N+2 줄 ~ N + M + K + 1번째 줄까지 세 개의 정수 a, b, c가 주어짐

a가 1인 경우 b(1 <=b <=N)번째 수를 c로 바꾸고

a가 2인 경우에는 b(1<=b <=N)번째수부터 c(b<=c<=N) 번째 수까지 합을 구하여 출력

 

주의사항

c의 값은 N개의 수처럼 100000이 넘기 때문에 long으로 받아야 한다. int로 받으면 NumberFormatException 발생 가능

input 형태로 들어오는 값은 항상 고정적인 값이 아니기 때문에 이에 대해 파악하고 작업하는 문제가 필요하다.

 

답

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

public class Main {

	static int N;
	static int M;
	static int K;
	static long inputArr[];
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);
		
		/**
		 * 첫 줄 입력
		 * 수의 갯수 N( 1<= N <=1000000)
		 * 수의 변경이 일어나는 횟수 M (1 <= M <= 10000)
		 * 구간의 합을 구하는 횟수 K (1 <= K <= 10000)
		 */
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		
		inputArr = new long[N +1];
		
		for(int i = 1; i < N+1; i++) {
			inputArr[i] = sc.nextLong();
		}
		
		SegmentTree segTree = new SegmentTree(inputArr);
		
		int counter = M + K;
		
		for(int i = 0; i < counter; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			long c = sc.nextLong();
			switch(a) {
			case 1:
				long diff = c - inputArr[b];
				inputArr[b] = c;
				segTree.update(1, N, 1, b, diff);
				break;
			case 2:
				System.out.println(segTree.sum(1, N, 1, b, c));
				break;
			}
		}
		
		sc.close();
	}
	
	static class SegmentTree {
		long segTree[];
		SegmentTree(long[] initArr) {
			segTree = new long[4*N]; // segmentTree의 크기는 4N을 넘지 않는다.
			init(initArr, 1, N, 1);;
		}
		
		long init(long[] arr, int left, int right, int node) {
			if(left == right) {
				return segTree[node] = arr[left];
			}
			
			int mid = (left + right) / 2;
			
			return segTree[node] = init(arr, left, mid, node *2)+  init(arr, mid + 1, right, node *2 +1);
			
		}
		
		long sum(int start, int end, int node, int left, long right) {
			if(left > end || right < start) {
				return 0;
			}
			if(left <= start && end <= right) {
				return segTree[node];
			}
			
			int mid = (start + end) / 2;
			return sum(start, mid, node*2, left, right) + sum(mid+1, end, node*2 + 1, left, right);
			
		}
		
		void update(int start, int end, int node, int index, long diff) {
			if(index < start || index > end) {
				return;
			}
			
			segTree[node] += diff;
			if(start == end) {
				return;
			}
			
			int mid = (start + end) /2;
			update(start, mid, node*2, index, diff);
			update(mid + 1, end, node*2 + 1, index, diff);
			
		}
	
	}
	
	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		StringTokenizer tokenizer = null;
		
		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}
		
		String nextToken() throws IOException {
			if(tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		
		int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	
		
		
	}

}