Lazy propagation

구간을 업데이트할 때 사용

vector<ll> lazy;

배열을 하나 만들어준다.

 

update_lazy() 함수

lazy[node] 값이 있다면

tree[node] += (end - start + 1) * lazy[node]; 해준다.

start != end이면

lazy propagation 하고,

비워준다.

lazy[node] = 0;

 

1. update_range() 함수

update_lazy() 함수 호출

 

a) 변경 범위가 탐색 구간에 없음

return;

 

b) 변경 범위가 탐색 구간 안에 있음

tree[node] += (end - start + 1) * diff;

하고

start != end이면

lazy[node*2], lazy[node*2 + 1]에 += diff 해준다.

 

c) 변경 범위 중 하나만 탐색 구간에 있음 -> Top-down

 

2. query

똑같다. 단지 update_lazy() 함수 호출이 제일 처음에 호출된다.

 

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

10999번: 구간 합 구하기 2

<소스코드>

#include <iostream>
#include <cmath>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> arr;
vector<ll> tree;
vector<ll> lazy;
 
void init(int node, int start, int end)
{
    if (start == end)
        tree[node] = arr[start];
    else
    {
        int mid = start + (end - start) / 2;
        init(node * 2, start, mid);
        init(node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}
 
void update_lazy(int node, int start, int end)
{
    if (lazy[node] != 0)
    {
        tree[node] += (end - start + 1) * lazy[node];
        
        //lazy propagation
        if (start != end)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void update_range(int node, int start, int end, int left, int right, long long diff)
{
    update_lazy(node, start, end);
 
    // 변경 idx 범위가 탐색 구간에 없음
    if (left > end || right < start)
        return;
 
    //  둘 다 변경 범위에 있음
    if (left <= start && end <= right)
    {
        tree[node] += (end - start + 1) * diff;
        if (start != end)
        {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    // 하나만 변경 범위에 있음
    int mid = start + (end - start) / 2;
    update_range(node * 2, start, mid, left, right, diff);
    update_range(node * 2 + 1, mid + 1, end, left, right, diff);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
 
ll query(int node, int start, int end, int left, int right)
{
    update_lazy(node, start, end);
 
    if (left > end || right < start)
        return 0;
 
    if (left <= start && end <= right)
        return tree[node];
 
    int mid = start + (end - start) / 2;
    ll lsum = query(node * 2, start, mid, left, right);
    ll rsum = query(node * 2 + 1, mid + 1, end, left, right);
    return lsum + rsum;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m, k;
    cin >> n >> m >> k;
 
    arr.resize(n);
 
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (h + 1));
    tree.resize(tree_size);
    lazy.resize(tree_size);
 
    init(1, 0, n - 1);
    m += k;
 
    while (m--)
    {
        int which;
        cin >> which;
        if (which == 1)
        {
            int left, right;
            long long diff;
            cin >> left >> right >> diff;
            update_range(1, 0, n - 1, left - 1, right - 1, diff);
        }
        else if (which == 2)
        {
            int left, right;
            cin >> left >> right;
            cout << query(1, 0, n - 1, left - 1, right - 1) << '\n';
        }
    }
    return 0;
}