백준 10999 (구간 합 구하기 2)

문제

10999번: 구간 합 구하기 2

저번에 풀었던 구간합 구하기 1  와 유사한 문제입니다.

차이점이라면 구간을 update하는 부분이 구간 모두에 정수 d를 더해준다는 것입니다.

 

이번에는 신촌 겨울캠프에서 배운 Lazy Segment Tree를 이용해서 풀었습니다.

const ll  n_ = 4 * 1e6 + 100;
ll tree[n_], lazy[n_], A[n_];

주어진 수를 받을 배열 A

A를 Segment tree로 바꿔줄 tree배열

lazy배열은 업데이트를 아직 하지 않은 값이 들어갑니다.

ll init(ll N, ll s, ll e) {
	if (s == e)return tree[N] = A[s];
	ll mid = (s + e) / 2;
	return tree[N] = init(N * 2, s, mid) + init(N * 2 + 1, mid + 1, e);
}

A배열을 Segment tree로 초기화 해주는 함수입니다.

기존의 segment tree 초기화 함수와 똑같습니다.

ll f(ll N, ll s, ll e, ll l, ll r) { //구간 합 구하는 함수
	update_lazy(N, s, e);
	if (l > e || r < s)return 0;
	if (l <= s && e <= r)return tree[N];
	ll mid = (s + e) / 2;
	return f(N * 2, s, mid, l, r) + f(N * 2 + 1, mid + 1, e, l, r);
}

구간 [l, r]을 구하는 함수입니다.

기존의 segment tree 구간 합 함수와 똑같습니다.

다른점이 있다면 맨 첫줄에 update_lazy함수가 있는데 이 함수는 propagate하는 부분입니다.

밑에서 다시 설명하겠습니다.

void update(ll N, ll s, ll e, ll l, ll r, ll val) {
    update_lazy(N, s, e);
    if (l > e || r < s)return;
    if (l <= s && e <= r) {
        tree[N] += (e - s + 1) * val;
        if (s != e) {
            lazy[N * 2] += val;
            lazy[N * 2 + 1] += val;
        }
        return;
    }
    ll mid = (s + e) / 2;
    update(N * 2, s, mid, l, r, val);
    update(N * 2 + 1, mid + 1, e, l, r, val);
    tree[N] = tree[N * 2] + tree[N * 2 + 1];
}

구간 [l, r] 포함하는 모든 수에 val을 더해주는 함수입니다. 

즉, update함수 입니다.

마찬가지로 처음에 update_lazy를 해주어 propagate할게 있으면 해줍니다.

4번째 줄을 보면 구간 [l, r]에 들어왔다는 의미입니다.

예를들어 구간 [3, 6]에 있는

모든 원소에 val를 더한다고 할때

빨간색 부분에만

tree[N] +(구간의 길이 * val)을 더해주면 됩니다.

 

 

 

 

빨간색 부분은 구간에 모두 포함하기 때문에 모든 원소에 val를 더해

update해주었습니다. 

당연히 빨간색 밑의 부분도 구간에 포함됩니다. 

밑의 부분은 나중에 update를 할 것이기 때문에 

lazy[N*2+1]와 lazy[2*N]에 val만큼 더해줍니다.

빨간색 부분 3은 s==e 이므로 그대로 놔둡니다.

 

12번째 줄부터는 기존 코드와 동일합니다.

void update_lazy(ll N, ll s, ll e) {
    if (!lazy[N])return;
    tree[N] += (e - s + 1) * lazy[N];
    if (s != e) {
        lazy[N * 2] += lazy[N];
        lazy[N * 2 + 1] += lazy[N];
    }
    lazy[N] = 0;
}

Propagate 해주는 함수입니다.

2번째 줄을 보면 lazy[N] ==0 이란 의미는 propagate할 부분이 없으므로 그대로 return 해주면 됩니다.

3번째 줄을 보면 이제 전에 val이 저장되있는 lazy[N]을 구간의 길이 만큼 곱해서 tree[N]에 넣어줍니다.

4번째 줄을 보면 lazy[N]에 저장되있던 val을 이제 밑의 단계에 propagate하는 부분입니다.

6번째 줄을 보면 이제 update가 완료되었으므로 lazy[N] = 0으로 초기화 해줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll  n_ = 4 * 1e6 + 100;
ll tree[n_], lazy[n_], A[n_];
ll n, m, k;
ll init(ll N, ll s, ll e);
ll f(ll N, ll s, ll e, ll l, ll r);
void update(ll N, ll s, ll e, ll l, ll r, ll val);
void update_lazy(ll N, ll s, ll e);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    init(1, 0, n - 1);
 
    ll key = m + k;
    while (key--) {
        ll a, b, c, d;
        cin >> a;
        if (a == 1) {
            cin >> b >> c >> d;
            update(1,0 ,n-1, b - 1, c - 1, d);
        }
        else {
            cin >> b >> c;
            cout<<f(1, 0, n - 1, b - 1, c - 1)<<'\n';
        }
    }
 
    return 0;
}
ll init(ll N, ll s, ll e) {
    if (s == e)return tree[N] = A[s];
    ll mid = (s + e) / 2;
    return tree[N] = init(N * 2, s, mid) + init(N * 2 + 1, mid + 1, e);
}
ll f(ll N, ll s, ll e, ll l, ll r) { //구간 합 구하는 함수
    update_lazy(N, s, e);
    if (l > e || r < s)return 0;
    if (l <= s && e <= r)return tree[N];
    ll mid = (s + e) / 2;
    return f(N * 2, s, mid, l, r) + f(N * 2 + 1, mid + 1, e, l, r);
}
void update(ll N, ll s, ll e, ll l, ll r, ll val) {
    update_lazy(N, s, e);
    if (l > e || r < s)return;
    if (l <= s && e <= r) {
        tree[N] += (e - s + 1) * val;
        if (s != e) {
            lazy[N * 2] += val;
            lazy[N * 2 + 1] += val;
        }
        return;
    }
    ll mid = (s + e) / 2;
    update(N * 2, s, mid, l, r, val);
    update(N * 2 + 1, mid + 1, e, l, r, val);
    tree[N] = tree[N * 2] + tree[N * 2 + 1];
}
void update_lazy(ll N, ll s, ll e) {
    if (!lazy[N])return;
    tree[N] += (e - s + 1) * lazy[N];
    if (s != e) {
        lazy[N * 2] += lazy[N];
        lazy[N * 2 + 1] += lazy[N];
    }
    lazy[N] = 0;
}