[백준온라인] 2042번 구간 합 구하기

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

2042번: 구간 합 구하기

문제 요약 : 주어진 위치를 수정하거나 구간의 합 출력

입력	출력
1 ≤ N(크기) ≤ 1000000 1 ≤ M(수정) ≤ 10000 1 ≤ K(합계) ≤ 10000 M+K 줄의 a, b, c a = 1일 때 b번째 수를 c로 바꿈[1 ≤ c ≤ long] a = 2일 때 b구간부터 c구간의 합 출력	주어진 위치 수정하거나 주어진 구간의 합 출력

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16464593	cbkpar	2042	맞았습니다!!	104320KB	468ms	Java	1976B

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

public class Main {
	
	static int n,m,sz;
	static long[] arr;
	static long[] tree;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int i;

		StringTokenizer st = new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		m+=Integer.parseInt(st.nextToken());
		
        //트리 생성을 위한 배열
		arr = new long[n];
		for(i=0;i<n;i++) arr[i] = Integer.parseInt(br.readLine());
		
        //트리 사이즈 측정
		sz = 1;
		for(i=1;i<n;i*=2) {
			if(i>=n) break;
			sz++;
		}
		sz = (int)Math.pow(2, sz);
		tree = new long[sz+1];
		init(0,n-1,1); // 트리 생성

		for(i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			if(Integer.parseInt(st.nextToken())==1) {//수정
				int b = Integer.parseInt(st.nextToken())-1;
				long c = Long.parseLong(st.nextToken());
				long dif = c-arr[b]; //원래 값으로 부터의 차이 계산
				arr[b]=c; // 기본 행렬에 넣어줌
				update(0,n-1,1,b,dif);
			}else {//출력
				int b = Integer.parseInt(st.nextToken())-1;
				int c = Integer.parseInt(st.nextToken())-1;
				sb.append(tsum(b,c,1,0,n-1)+"\n");//b부터 c구간 출력
				
			}
		}
		System.out.println(sb.toString());
	}
	
	static long init(int l, int r, int index) {
		if(l==r) {
			tree[index] = arr[l];
		}else {
			int mid = (l+r)/2;
			tree[index] = init(l,mid,index*2)+init(mid+1,r,index*2+1);
		}
		return tree[index];
	}
	
	static void update(int l, int r, int index ,int cindex, long diff) {
		if(l>cindex||cindex>r) return; //범위 벗어날 경우 리턴
		tree[index] += diff; // 차이만큼 더해줌
		if(l==r) return; // 더이상 쪼갤것이 없을 경우 리턴
		int mid = (l+r)/2; // 둘로 나눔
		update(l,mid,index*2,cindex,diff);
		update(mid+1,r,index*2+1,cindex,diff);
	}
	
	static long tsum(int l, int r, int index, int nodel, int noder) {
		if(r<nodel||noder<l) return 0;
		if(l<=nodel&&noder<=r) return tree[index];
		int mid = (nodel+noder)/2;
		return tsum(l,r,index*2,nodel,mid)+tsum(l,r,index*2+1,mid+1,noder);
	}
}

세그먼트 트리를 이용한 후 수정할 경우 트리를 수정해줘야 하는 작업이 생기지만 후에 부분합을 구할때 상당한 시간을 절약 할 수 있었다. 후에 시간 단축을 위해 lazy propagation을 이용해 트리를 수정하는 시간을 단축 할 수 있을 것 같다.