[백준 알고리즘] 2042번: 구간 합 구하기 (JAVA)

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

2042번: 구간 합 구하기

 

---

  소스코드

import java.util.*;
import java.io.*;

class Main {
    static long[] arr;
    static int a,b;
    static long c;

    public static class SegmentTree {
        long[] tree;
        int treeSize;

        public SegmentTree(int arrSize) {
            int h = (int) Math.ceil(Math.log(arrSize) / Math.log(2));
            this.treeSize = (int) Math.pow(2,h+1);
            tree = new long[treeSize];
        }

        public  long init(long[] tree, int node, int start, int end) {
            if (start == end) return tree[node] = arr[start];

            int mid = (start+end) / 2;
            return tree[node] = init(tree,node*2,start,mid) 
            					+ init(tree,node*2+1,mid+1,end);
        }

        public  void update(long[] tree, int node, int start, int end, int idx, long diff) {
            if (idx < start || idx > end) return;

            tree[node] += diff;

            int mid = (start+end) / 2;
            if (start != end) {
                update(tree,node*2,start,mid,idx,diff);
                update(tree,node*2+1,mid+1,end,idx,diff);
            }
        }

        public  long sum(long[] tree, int node, int start, int end, int left, int right) {
            if (left > end || right < start) return 0;

            if (left <= start && end <= right)  return tree[node];

            int mid = (start+end) / 2;
            return sum(tree,node*2,start,mid,left,right) 
              		+ sum(tree,node*2+1,mid+1,end,left,right);
        }

    }

    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 k = Integer.parseInt(st.nextToken());
        arr = new long[N+1];

        for (int i=1; i<=N;i++) {
            arr[i] = Long.parseLong(br.readLine());
        }

        SegmentTree sgTree = new SegmentTree(N);

        sgTree.init(sgTree.tree,1,1,N);

        for (int i=0; i< M+k;i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Long.parseLong(st.nextToken());

            if (a == 1) {
                 sgTree.update(sgTree.tree,1,1,N,b,c-arr[b]);
                 arr[b] = c;
            }
            else {
                sb.append(sgTree.sum(sgTree.tree,1,1,N,b,(int) c)).append("\n");
            }
        }
        System.out.println(sb);
    }
}

 

---

풀이

★세그먼트 트리를 사용하는 아주 기본적인 문제입니다 ! 구간의 합을 누적합이나 반복문으로 풀게 되면 시간초과가 발생하게 되고, 세그먼트 트리라는 알고리즘을 사용하여 풀어야 합니다 :) 

 

 

 

 

★ 세그먼트 트리 참고

https://hongjw1938.tistory.com/20

자료구조 - 세그먼트 트리(Segment Tree)