BOJ 10999

18 Feb 2020 • ProblemSolving

구간합 구하기 2

문제출처

문제 해석

  • 특정 구간을 업데이트하고, 구간합을 구하는 문제입니다.

설계(X)

  • 기본적인 하나의 값을 업데이트하는게 아닌, 구간을 업데이트하는 문제입니다.
  • 일반 세그먼트 트리를 이용하면 하나의 값을 업데이트하는데 O(logN)이고 최악의 경우에 구간 N개를 업데이트할 수 있습니다O(NlogN). 이를 M개의 쿼리에 대해 모두 업데이트를 할 때에 O(MNlogN)이라는 시간복잡도가 나와 시간내에 풀 수 없게 됩니다.
  • 업데이트를 O(logN)에 할 수 있는 Lazy propagation방법을 이용해야 하는 문제입니다. 처음보는 알고리즘이어서 멍멍멍님의 블로그를 참조하였습니다.
  • 각 트리에 lazy라는 값을 따로 주어 업데이트를 할 때마다 갱신시키지 않고 필요할 때만 갱신하도록 하는 알고리즘입니다.
  • [a,b]구간에 포함되는 최상단 노드를 찾아 lazy를 업데이트해주고, 만약 구간업데이트를 하거나 구간합을 구해야 하는 상황이 되었으면 노드를 타고 내려갈 때 각 lazy를 자식들에게 전파해주는 방식입니다.
  • 노드를 타고 내려갈 때, lazy값이 있으면 해당 노드의 값을 갱신시켜주고(+lazy값*구간길이) 0으로 초기화 해야하는 점에 유의해야 합니다.
  • 또한 구간업데이트를 할 때 구간에 포함되는 경우 해당 노드와 자식들을 업데이트를 할 수 있는데, 해당 노드의 조상노드들도 업데이트를 해야합니다. 재귀적 특성을 이용하여 모든 자식들의 업데이트를 마친 후에 재귀가 돌아올 때에 왼쪽자식과 오른쪽 자식의 값을 더해주어 조상노드도 업데이트를 할 수 있습니다.

구현(X)

코드
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 1000001
typedef long long ll;

int arr[MAXN];
vector<pair<ll,ll> > tree;
int N,M,K;
ll init(int node, int start ,int end){
    if (start == end) return tree[node].second = arr[start];
    int mid = (start +end) / 2;
    return tree[node].second = init(node*2,start,mid)+init(node*2+1,mid+1,end);
}
void update(int node ,int start , int end, int left, int right, ll diff){
    // lazy가 있을 때 현재 노드 갱신 후, 자식노드에게 전파 및 초기화
    if (tree[node].first != 0){
        tree[node].second += (end - start + 1)*tree[node].first;
        if (start != end){
            tree[node*2].first += tree[node].first;
            tree[node*2+1].first += tree[node].first;
        }
        tree[node].first = 0;
    }
    if (left > end || right < start ) return ;
    // 만족하는 조상노드를 찾았을 때
    if (left <= start && end <= right) {
        tree[node].second += (end-start+1)*diff;
        if (start != end){
            tree[node*2].first += diff;
            tree[node*2+1].first += diff;
        }
        return;
    }
    int mid = (start +end)/2;
    update(node*2,start,mid,left,right,diff);
    update(node*2+1,mid+1,end,left,right,diff);
    tree[node].second = tree[node*2].second + tree[node*2+1].second;
}
ll sum(int node, int start, int end, int left, int right){
    if (tree[node].first != 0){
        tree[node].second += (end - start + 1)*tree[node].first;
        if (start != end){
            tree[node*2].first += tree[node].first;
            tree[node*2+1].first += tree[node].first;
        }
        tree[node].first = 0;
    }
    if (left > end || right < start ) return 0;
    if (left <= start && end <= right) return tree[node].second;
    int mid = (start+end)/2;
    return sum(node*2,start,mid,left,right)+sum(node*2+1,mid+1,end,left,right);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    M += K;
    for (int i = 0; i < N; i++){
        cin >> arr[i];
    }
    int h = 1;
    while (h<N) h<<=1;
    tree = vector<pair<ll,ll> >(h*2);
    init(1,0,N-1);
    while (M--){
        int order;
        cin >> order;
        if (order==1){
            int left, right;
            ll diff;
            cin >> left >> right >> diff;
            update(1,0,N-1,left-1,right-1,diff);
        }
        else{
            int left,right;
            cin >> left >> right;
            cout << sum(1,0,N-1,left-1,right-1)<<"\n";
        }
    }
    return 0;
}
디버깅
  • 구간업데이트 시, 구간이 모두 포함되는 노드(만족하는 조상노드)가 나오면 원래는 lazy를 갱신하고 자식들을 타고 내려가야하는데, 이럴 필요가 없이 값자체를 바로 갱신시켜주면서 자식을 타고 내려가면 lazy를 다시 업데이트해주는 수고를 덜게 됩니다.
제출결과
  • 152ms

마무리

  • 세그먼트트리와 lazy propagation방법을 이용하여 구간을 업데이트하는 문제였습니다. 이로써 훨씬 최적화된 방법으로 구간을 업데이트를 할 수 있게 되었습니다.
 BOJ

Related Posts