[10999번] 구간 합 구하기 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Segment Tree :: http://www.crocus.co.kr/648

2. Segment Tree with Lazy Propagation :: http://www.crocus.co.kr/658

2번 문제 해결 사항의 링크에 이 문제에 대한 설명을 수록해 두었습니다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
ll init(vector<ll> &arr, vector<ll> &tree, int node, int start, int end)
{
    if (start == end)
        return tree[node] = arr[start];
 
    int mid = (start + end) / 2;
 
    return tree[node] = init(arr, tree, node * 2, start, mid) + init(arr, tree, node * 2 + 1, mid + 1, end);
}
 
void update_lazy(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end)
{
    // lazy가 0이면 return;
    if (lazy[node] == 0)
        return;
    
    // 자식 노드가 있는 수 만큼 lazy값에 곱하여 더한다.
    // 자식에게 lazy를 분배하니 자식이 return으로 더해주지 못한 값을 직접 더한다.
    tree[node] += (end - start + 1) * lazy[node];
 
    // leaf가 아니면
    // 자식에게 lazy를 물려준다.
    if (start != end)
    {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
 
    // 물려준 후 lazy는 초기화
    lazy[node] = 0;
    
}
 
void update_range(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right, ll val)
{
    /*
        순서 ::
        1. lazy가 존재하면 업데이트 해준다.(tree[node] 변화)
        2. val을 더해준다.(자식수가 있는 만큼)
        2에서 자식 수만큼 더해주는 이유는 자식들은 아직 lazy가 업데이트 되지 않았기 때문
    */
    // 현재 노드에 lazy가 있는지 확인 후, lazy가 있다면 node를 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    // 하나도 속하지 않는다면 return;
    if (left > end || right < start)
        return;
 
    // 원하는 구간 내에 있는 노드에 왔을 경우
    if (left <= start && end <= right)
    {
        // 자식 노드가 있는 수 만큼 val을 곱해서 더해준다.
        // 자식이 return으로 더해주는 형태가 아니니 직접 더한다.
        tree[node] += (end - start + 1) * val;
 
        if (start != end)
        {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
 
    int mid = (start + end) / 2;
    update_range(tree, lazy, node * 2, start, mid, left, right, val);
    update_range(tree, lazy, node * 2 + 1, mid + 1, end, left, right, val);
 
    // 구간이 걸쳐서 속해 있다면 자식 노드를 이용하여 부모 노드를 업데이트 한다.
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
ll sum(vector<ll> &tree, vector<ll> &lazy, int node, int start, int end, int left, int right)
{
    // update이후 남은 lazy를 해당하는 구간을 sum 할 때 업데이트 해준다.
    update_lazy(tree, lazy, node, start, end);
 
    if (left > end || right < start)
        return 0;
 
    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()
{
    int n, m, k;
 
    scanf("%d %d %d", &n, &m, &k);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (1 + h));
 
    vector<ll> arr(n);
    vector<ll> tree(tree_size);
    vector<ll> lazy(tree_size);
 
    for (int i = 0; i < n; i++)
        scanf("%lld", &arr[i]);
 
    init(arr, tree, 1, 0, n - 1);
    m += k;
 
    while (m--)
    {
        int num;
        scanf("%d", &num);
 
        if (num == 1)
        {
            int left, right;
            ll val;
 
            scanf("%d %d %lld", &left, &right, &val);
 
            update_range(tree, lazy, 1, 0, n - 1, left-1, right-1, val);
        }
 
        else if (num == 2)
        {
            int left, right;
            scanf("%d %d", &left, &right);
 
            printf("%lld\n",sum(tree, lazy, 1, 0, n - 1, left-1, right-1));
        }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>