[백준 / BOJ] 10999 구간 합 구하기 2

문제

출처 : www.acmicpc.net/problem/10999

10999번: 구간 합 구하기 2

수의 개수 N, M, K가 주어진다.

M은 수의 변경이 일어나는 횟수이고, K는 각 구간의 합을 구하는 횟수이다.

 

앞의 수에 따라서, 변경, 합을 구하면되는데,

1은 변경이고 2는 구간합이다.

예를들어,

1 1 5 10 이 나오면,

1부터 5범위까지 +10을 해주면된다.

 

 

풀이

N의 최댓값이 1,000,000이고, M과 K가 각각 10,000이므로 완전탐색으로 풀경우 N*(M+K) 번 반복하여 시간초과가 난다.

기본적인 세그먼트 트리로 풀어도 시간초과가 났는데,

 

시간초과 소스코드

// 시간초과 소스코드

//  main.cpp

//  10999 구간 합 구하기 2

//

//  Created by 이준영 on 2020/12/28.

//

 

#include <iostream>

 

using namespace std;

 

int N, M, K;

long long arr[1000005], seg[1000005 * 4 + 5];

long long num;

 

long long set(int left, int right, int idx){

    if(left > right){

        return 0;

    }

    if(left == right){

        return seg[idx] = arr[left];

    }

    int mid = (left + right) / 2;

    return seg[idx] = set(left, mid, idx*2) + set(mid+1, right, idx*2+1);

}

 

long long update(int left, int right, int idx, int tl, int tr, int tn){

    if(left >= tl and right <= tr){

        seg[idx] = seg[idx] + (tn * ((right - left) + 1));

    }

    if(right < tl or left > tr or left >= right){

        return seg[idx];

    }

    int mid = (left + right) / 2;

    return seg[idx] = update(left, mid, idx*2, tl, tr, tn) + update(mid+1, right, idx*2+1, tl, tr, tn);

}

 

long long search(int left, int right, int idx, int sl, int sr){

    if(right < sl or left > sr){

        return 0;

    }

    if(left >= sl and right <= sr){

        return seg[idx];

    }

    int mid = (left + right) / 2;

    return num = search(left, mid, idx*2, sl, sr) + search(mid+1, right, idx*2+1, sl, sr);

}

 

int main(int argc, const char * argv[]) {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    cin >> N >> M >> K;

    for(int i = 1; i <= N; i++){

        cin >> arr[i];

    }

    set(1,N,1);

    for(int i = 1; i <= M+K; i++){

        int a, b, c, d;

        cin >> a;

        if(a == 1){

            cin >> b >> c >> d;

            update(1, N, 1, b, c, d);

        }

        else{

            cin >> b >> c;

            num = 0;

            cout << search(1, N, 1, b, c) << "\n";

        }

    }

    return 0;

}

 

구간합을 구하는데 걸리는 시간 : logN

한번 업데이트에 걸리는 시간 : NlogN 

-> 입력의 범위가 1~5라고 하고, 구간합을 구해야할 범위가 3~4라고하면, 한번업데이트시, 결국 노드의 끝까지 업데이트해야 구간합을 구할수있음

 

lazy propagation을 이용해 풀어야했다.

lazy propagation은 현재 값을 당장 업데이트할 필요가 없다면, 일단 배열에 저장해놓고, 나중에 업데이트할 필요가 있을때, 한번에 업데이트하는 방법이다.

 

예를들어,

업데이트 할 값의 범위가 1~3이고, 현재 보고있는 범위가 1~3이라면,

그 아래 하위노드인 1~2, 3를 업데이트 하는것이 아닌, 일단 1~3만 업데이트하고 lazy배열에 값을 저장해놓는다.

만약 1 1 3 -1 을 입력받았다면,

1~3 범위는 -3 으로 업데이트 되어있고,

1~2에 해당하는 lazy = -1 

3에 해당하는 lazy = -1

로 초기화 된다.

 

나중에 업데이트를 하거나, 구간합을 구할때, 해당 idx의 lazy값이 초기상태가 아니라면, 저장해놓은 lazy값을 더하고 출력한다.

이때, 현재 노드의 하위노드로 lazy값을 전달해줘야한다. (하위노드 또한 해당 lazy값을 가져와서 업데이트 해야할수 있으므로..)

 

처음에는 구간합을 구할때만 lazy propagation을 사용하면 될것이라고 생각해서, lazy배열에 값을 계속 중첩해놓다가 사용할때만 더하는 방식으로 구현했는데, 문제의 범위가 long long 이라 이런식으로 하면 범위를 벗어난다.

update와 구간합을 구하는 연산 둘 모두 해당 인덱스를 지나가야한다면, lazy값을 전파하면서 초기화 시켜주자.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10999%20%EA%B5%AC%EA%B0%84%20%ED%95%A9%20%EA%B5%AC%ED%95%98%EA%B8%B0%202/main.cpp

devxb/JJUNalgo