<Algorithm> 60. 2042번 구간 합 구하기

1. 2042번 구간 합 구하기

• Segment Tree를 활용하는 문제, 인덱스의 범위, 구간의 범위에 대한 생각이 필요한 문제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class Main {     static int[] arr;     static long[] tree = new long[1<<21];         public static void main(String[] args) throws NumberFormatException, IOException {         BufferedReader br =new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         ArrayList<Long> ans = new ArrayList<>();         int N = Integer.parseInt(st.nextToken());         int M = Integer.parseInt(st.nextToken()); // 변경횟수         int K = Integer.parseInt(st.nextToken()); // 구간합 횟수         arr = new int[10000001];         for(int i = 1; i <= N; i ++) {             arr[i] = Integer.parseInt(br.readLine()); // 구간합 횟수         }         arr[0]=0;         init(1, 1, N);                  for(int i = 0; i < M + K; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken()); // 변경횟수             int c = Integer.parseInt(st.nextToken()); // 구간합 횟수             if(a==1) {                 long diff = (long)c-arr[b];                 arr[b] = c;                 update(1, 1, N, diff, b);             }else {                 ans.add(sum(1, 1, N, b, c));             }         }                          for(Long lo: ans) System.out.println(lo);                                }          private static long init(int node, int start, int end) {         if(start == end) {             return tree[node] =(long)arr[start];// 단말노드         }else {                  return tree[node] = init(node * 2, start, (start + end)/2)                      + init(node * 2 + 1, (start + end)/2 + 1, end);         }     }          private static void update(int node, int start, int end, long diff, int changeIndex) {         if(start > changeIndex || end < changeIndex) {             return;         }                 tree[node] = tree[node] + diff;                  if(start != end) {             update(node*2, start, (start+end)/2, diff, changeIndex);             update(node*2+1, (start+end)/2 + 1, end, diff, changeIndex);         }     }          private static long sum(int node, int start, int end, int left, int right) {                  if(end < left || start > right  ) {             return 0;// ex 구간이 4 ~ 7 인데 1 ~ 3일 경우         }else if(start >= left && end <= right) {             return tree[node];                      }else{             return sum(node*2, start, (start+end)/2, left, right)  + sum(node*2+1, (start+end)/2 + 1, end, left, right);         }                       }      } Colored by Color Scripter

cs

출처 : https://www.acmicpc.net/blog/view/9