[16975] 수열과 쿼리 21

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

16975번: 수열과 쿼리 21

<문제>

느리게 갱신되는 세그먼트 트리 문제이다.

느리게 갱신하는 이유는, '구간'으로 업데이트가 이루어지기 때문이다.

당장 필요한 구간이 아니라면 바로 업데이트하지 않고, 꼭 필요할때까지 업데이트를 미루는것이
기본 세그트리와 다른점이다.

일반적인 세그먼트 트리에서 T개의 구간을 갱신하려면, TlogN의 시간복잡도가 나올것이다.

 

만약 입력이 아래와 같다고 생각해보자.

2~n까지 1을 더하라는 업데이트 쿼리 M-1개

1을 출력하라는 출력쿼리 1개

업데이트를 M-1번 수행 * 구간 길이 T-1, N=100000일때 log2(100000)==16

O(M*TlogN)이 나오고, 10만*10만*16 정도의 연산횟수를 갖는다. 이는 시간제한 2초를 만족시킬 수 없다.

 

이때 Lazy propagation 기법을 사용하면 시간복잡도를 O(MTlogN) -> O(logN)으로 획기적으로 줄일 수 있다.

업데이트 쿼리는 최대 10만번 들어오고, N역시 10만이므로, 약 160만정도의 연산횟수를 갖게된다.

이는 시간제한을 만족한다.

 

<소스코드>

#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
typedef long long ll;
int n, m;
vector <ll>num;
vector <ll>segTree;
vector <ll>lazy;
vector <pair<pair<int, int>, pair<int, ll>>>cmd;
void updateLazy(int node, int start, int end);
ll makeSegTree(int node, int start, int end) {
    if (start == end)return segTree[node] = num[start];
    int mid = (start + end) / 2;
    return segTree[node]=makeSegTree(node*2,start,mid)
        +makeSegTree(node*2+1,mid+1,end);
}
ll query(int node, int start, int end, int idx) {
    updateLazy(node, start, end);
    if (end < idx || idx < start)return 0;
    if (idx <= start && end <= idx)return segTree[node];
    if (start != end) {
        int mid = (start + end) / 2;
        return query(node * 2, start, mid, idx)
            + query(node * 2 + 1, mid + 1, end, idx);
    }
}
void updateLazy(int node, int start, int end) {
    if (lazy[node] != 0) {
        segTree[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
void updateSegTree(int node, int start, int end, int left, int right, ll diff) {
    updateLazy(node, start, end);
    if (end < left || right < start)return;
    if (left <= start && end <= right) {
        segTree[node] += (end - start + 1) * diff;
        if (start != end) {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
    int mid = (start + end) / 2;
    updateSegTree(node * 2, start, mid, left, right, diff);
    updateSegTree(node * 2 + 1, mid + 1, end, left, right, diff);
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
int main(void) {
    int i, j;
    scanf("%d", &n);
    segTree.resize(4 * n);
    lazy.resize(4 * n);
    num.resize(n + 2);
    for (i = 1; i <= n; i++) {
        scanf("%lld", &num[i]);
    }
    makeSegTree(1, 1, n);
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        int A;
        scanf("%d", &A);
        if (A == 1) {
            int s, e;
            ll value;
            scanf("%d %d %lld", &s, &e, &value);
            updateSegTree(1, 1, n, s, e, value);
        }
        else if (A == 2) {
            int number;
            scanf("%d", &number);
            printf("%lld\n", query(1, 1, n, number));
        }
    }
    return 0;
}