백준 2042 : 구간 합 구하기 - 세그먼트 트리

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

2042번: 구간 합 구하기

 

[JAVA]

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n, m, k;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        long a[] = new long[n];
        int h = (int) Math.ceil(Math.log10(n) / Math.log10(2));
        int tree_size = (1 << (h + 1));
        long tree[] = new long[tree_size];
        m += k;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(br.readLine());
        }
        init(a, tree, 1, 0, n - 1);

        StringBuilder sb = new StringBuilder();
        while (m-- > 0) {
            int t1, t2, t3;
            st = new StringTokenizer(br.readLine());
            t1 = Integer.parseInt(st.nextToken());
            if (t1 == 1) {
                long t4;
                t2 = Integer.parseInt(st.nextToken());
                t4 = Long.parseLong(st.nextToken());
                t2 -= 1;
                long diff = t4 - a[t2];
                a[t2] = t4;
                update(tree, 1, 0, n - 1, t2, diff);
            } else if (t1 == 2) {
                t2 = Integer.parseInt(st.nextToken());
                t3 = Integer.parseInt(st.nextToken());
                sb.append(sum(tree, 1, 0, n - 1, t2 - 1, t3 - 1) + "\n");
            }
        }
        System.out.println(sb);
        br.close();
    }

    static long init(long[] a, long[] tree, int node, int start, int end) {
        if (start == end)
            return tree[node] = a[start];
        else
            return tree[node] = init(a, tree, node * 2, start, (start + end) / 2)
                    + init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
    }

    static void update(long[] tree, int node, int start, int end, int index, long diff) {
        if (index < start || index > end)
            return;
        tree[node] = tree[node] + diff;
        if (start != end) {
            update(tree, node * 2, start, (start + end) / 2, index, diff);
            update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
        }
    }

    static 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];
        return sum(tree, node * 2, start, (start + end) / 2, left, right)
                + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }

}

 

 

 

---

 

세그먼트 트리 (Segment Tree)