[Java] 백준 10999번 합 구하기 - Lazy Segment Tree

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

10999번: 구간 합 구하기 2

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

public class p5_10999 {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int n, m;
    static long[] val, tree, lazy;

    public static void main(String[] args) {
        n = fs.nextInt();
        m = fs.nextInt() + fs.nextInt();

        val = new long[n + 1];
        tree = new long[n * 4];
        lazy = new long[n * 4];

        for (int i=1;i<=n;i++) val[i] = fs.nextLong();
        init(1, n, 1);

        while (m-- > 0){
            int flag = fs.nextInt();
            if (flag == 1){
                int left = fs.nextInt(), right = fs.nextInt();
                long value = fs.nextLong();

                update(1, n, 1, left, right, value);
            }
            else{
                int left = fs.nextInt(), right = fs.nextInt();
                pw.println(sum(1, n, 1, left, right));
            }
        }
        
        pw.close();
    }

    static void update(int lo, int hi, int node, int left, int right, long value){
        lazy(lo, hi, node);

        if (hi < left || right < lo) return;
        if (left <= lo && hi <= right){
            tree[node] += (hi - lo + 1) * value;
            if (lo != hi){
                lazy[node * 2] += value;
                lazy[node * 2 + 1] += value;
            }
            return;
        }

        int mid = (lo + hi) / 2;
        update(lo, mid, node * 2, left, right, value);
        update(mid + 1, hi, node * 2 + 1, left, right, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    static void lazy(int lo, int hi, int node){
        if (lazy[node] != 0){
            tree[node] += lazy[node] * (hi - lo + 1);
            if (lo != hi){
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    static long sum(int lo, int hi, int node, int left, int right){
        lazy(lo, hi, node);

        if (hi < left || right < lo) return 0;
        if (left <= lo && hi <= right) return tree[node];

        int mid = (lo + hi) / 2;
        return sum(lo, mid, node * 2, left, right) + sum(mid + 1, hi, node * 2 + 1, left, right);
    }

    static long init(int left, int right, int node){    
        if (left == right) return tree[node] = val[left];

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

    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}