BOJ -2268 ) 수들의 합

 

 

---

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

2268번: 수들의 합

 

---

세그먼트트리의 기본꼴인 연속합을 구하는 문제이다.

 

세그먼트트리는 O(NM)의 시간복잡도를 O(LogN)으로 줄여주는 자료구조이다.

 

기본예제를 충분히 연습하고 Fenwick 트리로 넘어가야겠다.

---

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

public class 수들의합 {
	public static long number[] , 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 m = Integer.parseInt(st.nextToken());
		int size = (int) Math.pow(2, 1+Math.ceil(Math.log10(n) / Math.log10(2)));
		number = new long[n];
		seg = new long[size];
		for(int i = 0 ; i < m ; i ++) {
			st = new StringTokenizer(br.readLine());
			int order = Integer.parseInt(st.nextToken());
			if(order ==1) {
				// modify
				int t = Integer.parseInt(st.nextToken())-1;
				int c = Integer.parseInt(st.nextToken());
				long d = c-number[t];
				number[t] = c;
				Modify(1 , 0 , n-1 , t , d);
			} else {
				//sum
				int s = Integer.parseInt(st.nextToken())-1;
				int e = Integer.parseInt(st.nextToken())-1;
				if(e < s) {int t = s; s = e ; e =t;}
				sb.append(sum(1,0,n-1,s,e)+ "\n");
			}
		}System.out.println(sb);
	}
	private static void Modify(int node, int start, int end, int tar, long diff) {
		if(tar > end || start > tar) {
			return ;
		}
		seg[node] += diff;
		 if(start != end) {
			Modify(2*node, start, (start+end)>>1, tar, diff);
			Modify(2*node+1, ((start+end)>>1)+1, end, tar, diff);
		}
	}
	private static long sum(int node, int start, int end, int left, int right) {
		if(left > end || start > right) {
			return 0;
		} else if(left <= start && end <= right){
			return seg[node];
		} else {
			return sum (2*node , start , (start+end)>>1 , left , right ) + sum( 2*node+1 , ((start+end)>>1)+1 , end , left, right);
		}
	}
}

---