백준 : 109999 (JAVA)

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

10999번: 구간 합 구하기 2

게으른 전파 알고리즘

 

기존 세그먼트 트리에서 구간의 업데이트를 해주엇을때 모든 노드를 방문하면서 업데이트하는것이아니라 대표값만 업데이트해놧다가 필요한 순간에만 업데이트해서 사용하는 기법.

 

package D0227;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B10999 {
    static int N, M, K;
    static long node[];
    static long laze[];
    static int arr[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        node = new long[N * 4];
        laze = new long[N * 4];
        arr = new int[N + 1];
 
        for (int n = 1; n <= N; n++) {
            arr[n] = Integer.parseInt(br.readLine());
        }
 
        Init(1, N, 1);
        StringBuilder sb = new StringBuilder();
        for (int m = 0; m < M + K; m++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if (a == 1) {
                int d = Integer.parseInt(st.nextToken());
                change(1, N, b, c, d, 1);
            } else {
//                System.out.println(sum(1, N, b, c, 1));
                sb.append(sum(1, N, b, c, 1) + "\n");
            }
        }
        System.out.println(sb.toString());
    }
 
    public static void laze_update(int start, int end, int n) {
        if (laze[n] == 0)
            return;
 
        node[n] += ((end - start + 1) * laze[n]);
        if (start != end) {
            laze[n * 2] += laze[n];
            laze[n * 2 + 1] += laze[n];
        }
 
        laze[n] = 0;
 
    }
 
    public static long Init(int start, int end, int n) {
        if (start == end) {
            return node[n] = arr[start];
        }
        int mid = (start + end) / 2;
 
        return node[n] = Init(start, mid, n * 2) + Init(mid + 1, end, n * 2 + 1);
    }
 
    public static long sum(int start, int end, int i, int j, int n) {
        laze_update(start, end, n);
 
        if (j < start || end < i)
            return 0;
 
        if (i <= start && end <= j)
            return node[n];
 
        int mid = (start + end) / 2;
 
        return sum(start, mid, i, j, n * 2) + sum(mid + 1, end, i, j, n * 2 + 1);
    }
 
    public static void change(int start, int end, int b, int c, long d, int n) {
        laze_update(start, end, n);
        if (end < b || start > c)
            return;
        if (b <= start && end <= c) {
            laze[n] += d;
            laze_update(start, end, n);
            return;
        }
 
        int mid = (start + end) / 2;
 
        change(start, mid, b, c, d, n * 2);
        change(mid + 1, end, b, c, d, n * 2 + 1);
        node[n] = node[n * 2] + node[n * 2 + 1];
    }
}