골드에그

1. 문제요약

10999번: 구간 합 구하기 2 (acmicpc.net)

어떤 연속된 N개의 수가 있다. 수의 변경이 빈번히 일어나고 연속 구간에 대한 부분합을 구하려고 한다.

2. 문제예제

3. 팩트추출

Fact 1 : 연속된 1차원 공간에서 내부에 있는 값들이 수시로 변경되고 연속 부분 구간에 대한 연산을 수행하기 때문에 세그먼트 트리를 생각해볼 수 있다. (내부 값들이 수시로 변경되기 때문에 부분합 자료구조 불가능)
 

Fact 2 : 비슷한 문제인 2042번: 구간 합 구하기 (acmicpc.net) 와 다른 부분은 업데이트 부분이 "구간" 이라는 점이다. 2042 문제같은 경우 단일 지점만 업데이트 되기 때문에 한 번 쿼리 수행 시 시간복잡도가 O(Q * lgN) 이 되지만, 이 문제의 경우 구간 전체를 업데이트 해야 되기 때문에 한 번 쿼리 수행 시 시간복잡도가 O(Q * MlgN) 이 된다. (여기서 M은 구간의 길이) 일반적인 세그먼트 트리를 사용할 경우 시간 초과가 발생할 수 있다.

Fact 3 :  lgN 트리 길이만큼 매번 연산하지 말고, 업데이트나 조회 시 해당 구간이 필요하면 변수를 하나 두어 해당 변수에 업데이트하고 다음 번에 도착했을 때 한 단계씩 자식에게 값을 늦게 전파하면 연산을 획기적으로 줄일 수 있다. 이러한 방법을 Lazy Propagation 이라고 한다. 자세한 내용은 다음 글을 참고하자.

[알고리즘] Segment Tree :: 골드에그 (tistory.com)

4. 문제풀이(수동)

(...생략...)

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. Segment Tree 와 Lazy Propagation 을 활용하여 문제를 풀었다.

6. 소스코드

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

class Main {
    static int n;
    static long[] elements;
    static class SegmentTree {
        static class Node {
            long value;
            long lazy;
            Node leftChild, rightChild;
        }

        static Node getNode() {
            Node temp = new Node();
            temp.value = 0;
            temp.lazy = 0;
            temp.leftChild = null;
            temp.rightChild = null;
            return temp;
        }

        static void updateLazy(Node node, int left, int right) {
            // 만약 현재 노드에 lazy 값이 있다면
            if (node.lazy != 0) {
                // 만약 자식이 있다면 자식들에게 lazy 값을 전파한다.
                if (node.leftChild != null) {
                    node.leftChild.lazy += node.lazy;
                }
                if (node.rightChild != null) {
                    node.rightChild.lazy += node.lazy;
                }
                // 현재노드 업데이트 ( 부모노드이므로 구간 길이만큼 업데이트 )
                node.value += node.lazy * (right - left + 1);
                // lazy 값을 업데이트했으므로 0으로 만들어준다.
                node.lazy = 0;
            }
        }

        // 초기화
        private static void initTree(Node node, int index, long updateValue, int left, int right) {
            // 기저사례 (구간에 index 가 없는 경우)
            if (index < left || index > right)
                return;

            // 기저사례 (마지막 구간에 index 가 있는 경우 (수정할 필요 없는 경우))
            // 초기화 과정이 없기 때문에 필요
            if (left == right) {
                node.value = updateValue;
                return;
            }

            int mid = left + (right - left) / 2;
            long leftSum = 0, rightSum = 0;

            if (index <= mid) {
                if (node.leftChild == null) {
                    node.leftChild = getNode();
                }
                initTree(node.leftChild, index, updateValue, left, mid);
            } else {
                if (node.rightChild == null) {
                    node.rightChild = getNode();
                }
                initTree(node.rightChild, index, updateValue, mid + 1, right);
            }

            if (node.leftChild != null)
                leftSum = node.leftChild.value;
            if (node.rightChild != null)
                rightSum = node.rightChild.value;
            node.value = leftSum + rightSum;
        }

        private static void updateRange(Node node, long updateValue, int updateStart, int updateEnd, int left, int right) {
            updateLazy(node, left, right);
            // 기저사례 (구간에 쿼리구간이 없는 경우)
            if (updateEnd < left || updateStart > right)
                return;

            // 기저사례 (업데이트 구간이 완전히 포함되는 경우)
            if (updateEnd >= right && updateStart <= left) {
                node.value += (updateValue * (right - left + 1));
                if (node.leftChild != null) {
                    node.leftChild.lazy += updateValue;
                }
                if (node.rightChild != null) {
                    node.rightChild.lazy += updateValue;
                }
                return;
            }

            int mid = left + (right - left) / 2;
            updateRange(node.leftChild, updateValue, updateStart, updateEnd, left, mid);
            updateRange(node.rightChild, updateValue, updateStart, updateEnd, mid + 1, right);
            node.value = node.leftChild.value + node.rightChild.value;
        }

        static long query(Node node, int queryStart, int queryEnd, int left, int right) {
            updateLazy(node, left, right);
            // 기저사례 (할당되지 않은 경우)
            if (node == null)
                return 0;

            // 기저사례 (구간에 쿼리구간이 없는 경우)
            if (queryEnd < left || queryStart > right)
                return 0;

            // 기저사례 (쿼리 구간이 완전히 포함되는 경우)
            if (queryEnd >= right && queryStart <= left) {
                return node.value;
            }

            int mid = left + (right - left) / 2;
            return query(node.leftChild, queryStart, queryEnd, left, mid) + query(node.rightChild, queryStart, queryEnd, mid + 1, right);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        elements = new long[n];
        for(int i=0; i<n; i++) {
            elements[i] = Long.parseLong(br.readLine());
        }

        SegmentTree.Node root = new SegmentTree.Node();

        for (int i=0; i<elements.length; i++)
            SegmentTree.initTree(root, i+1, elements[i], 1, n);

        for(int i=0; i<m+k; i++) {
            st = new StringTokenizer(br.readLine());
            int operation = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if(operation == 1) {
                long updateValue = Long.parseLong(st.nextToken());
                SegmentTree.updateRange(root, updateValue, left, right, 1, n);
            }else {
                bw.write(SegmentTree.query(root, left, right, 1, n)+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
}