[자바]백준 2042번 구간 합

안녕하세요. 개발자 움탱입니다.
이 기사는 알고리즘을 공부하면서 공부를 추적하기 위한 것입니다.
그래서 설명마다 일기장으로 편하게 쓰려고 하고 짧은 언어 형식으로 쓰려고 합니다.
그리고 더 좋은 시각이 있으시거나 잘 모르시는 부분이 있으시면 알려주시면 정말 감사하겠습니다.
좋은 하루 보내세요 🙂

쉬운 목차

문제가 있는 링크

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

23.04.18 신정동복싱대한복싱체육관 양천구 복싱목동복싱신월동복싱복싱다이어트

문제 설명

구간의 합을 구하는 문제는 단순히 문제에 주어진 구간의 합을 계산하는 문제입니다.

그러나 평균 숫자가 변경되고 그에 따라 새 합계가 계산됩니다.

논평

나는 단지 간격의 합을 찾을 것이라고 생각했고, 간격을 얻을 때마다 반복문을 뒤집어 답을 계산할 것이라고 생각했습니다. 루프를 실행하면 최대 자릿수가 2^63이므로 시간이 초과됩니다.날수있다

이 문제는 일반적인 세그먼트 트리 문제입니다.오전.

우선 세그먼트 트리를 공부하고 풀어서 연습하는 것이 좋은 작업입니다.

아래는 백준의 세그먼트 트리에 대해 보도한 기사입니다.

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

세그먼트 트리

기사가 업데이트되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고 다음 두 작업을 수행해야 하는 문제를 생각해 봅시다. 구간 l과 r이 주어지면(l ≤ r), A(l) + A(l+1) + ..

www.acmicpc.net

암호

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

public class Main {
    public static void main(String() args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 수의 개수
        int M = Integer.parseInt(st.nextToken()); // 수의 변경이 일어나는 횟수
        int K = Integer.parseInt(st.nextToken()); // 구간의 합을 구하는 횟수

        long() arr = new long(N + 1);

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

        SegmentTree segment = new SegmentTree(arr);
        segment.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());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) {
                segment.update(1, 1, N, b, c - segment.getArr()(b));
                segment.updateArr(b, c);
            } else {
                System.out.println(segment.sum(1, 1, N, b, (int)c));
            }
        }

        br.close();
    }
}

class SegmentTree {
    private long() tree;
    private long() arr;

    public SegmentTree(long() arr) {
        int height = (int)Math.ceil(Math.log(arr.length - 1) / Math.log(2));

        tree = new long((int)Math.pow(2, height + 1));
        this.arr = arr;
    }

    public long init(int node, int start, int end) {
        if (start == end) {
            return this.tree(node) = this.arr(start);
        }

        return this.tree(node) = init(node * 2, start, (start + end) / 2) +
                init(node * 2 + 1, (start + end) / 2 + 1, end);
    }

    public void update(int node, int start, int end, int idx, long diff) {
        if (idx < start || end < idx) {
            return;
        }

        this.tree(node) += diff;

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

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

        if (left <= start && end <= right) {
            return this.tree(node);
        }

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

    public long() getArr() {
        return this.arr;
    }

    public void updateArr(int idx, long value) {
        this.arr(idx) = value;
    }
}