[10999] 구간 합 구하기 2

구간 합 구하기1처럼 풀면 시간초과가 나는 문제입니다.

Lazy Propagation + 세그먼트 트리를 섞어서 해결해야하는 문제입니다.
저도 Lazy Propagation ??이라는 알고리즘은 처음 보는데요.

개념은 간단합니다. 지금 할 필요 없는 일은 미루는 개념입니다. 굉장히 게으른 알고리즘이지만 효율이 굉장히 좋은 것 같습니다.

설명 : https://www.acmicpc.net/blog/view/26

여기에 설명이 매우 잘 나와있습니다.

제 코드입니다. 궁금하신건 댓글 달아주시면 무조건 답변 달아드립니다.

#include <iostream>
#include <vector>
#include <cmath>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
 
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e6
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int arr[MAX_SIZE];
 
ll init(vll &tree, int node, int start, int end) {
    if (start == end) return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
    return tree[node] = init(tree, node * 2, start, mid) + init(tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vll &tree, vll &lazy, int node, int start, int end) {
    if (lazy[node] != 0) {
        tree[node] += lazy[node] * (end - start + 1);
 
        if (start != end) { //leaf노드가 아닐 때만 전파
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
ll update_range(vll &tree, vll &lazy, int node, int start, int end, int left, int right, ll add) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return tree[node];
    else if (left <= start && end <= right) {
        tree[node] += add * (end - start + 1);
 
        if (start != end) {
            lazy[node * 2] += add;
            lazy[node * 2 + 1] += add;
        }
 
        return tree[node];
    }
 
    int mid = (start + end) / 2;
    return tree[node] = update_range(tree, lazy, node * 2, start, mid, left, right, add) + update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, add);
}
 
ll sum(vll &tree, vll &lazy, int node, int start, int end, int left, int right) {
    update_lazy(tree, lazy, node, start, end);
 
    if (right < start || end < left) return 0;
    else if (left <= start && end <= right) return tree[node];
 
    int mid = (start + end) / 2;
    return sum(tree, lazy, node * 2, start, mid, left, right) + sum(tree, lazy, node * 2 + 1, mid + 1, end, left, right);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
 
    int height = (int)ceil(log2(n));
    vll tree(1 << (height + 1));
    vll lazy(1 << (height + 1));
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    init(tree, 1, 0, n - 1);
 
    for (int i = 0; i < m + k; i++) {
        int cmd, a, b;
        ll add;
        cin >> cmd >> a >> b;
        a--, b--;
 
        if (cmd == 1) {
            cin >> add;
            update_range(tree, lazy, 1, 0, n - 1, a, b, add);
        }
        else {
            cout << sum(tree, lazy, 1, 0, n - 1, a, b) << '\n';
        }
    }
 
    return 0;
}