하늘에서 떨어지는 1, 2, ... , R-L+1개의 별( BOJ 17353 )

문제 : https://www.acmicpc.net/problem/17353

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

 

문제 파악하기

주어진 N개의 수열을 대상으로 [ L, R ] 구간에 1, 2, ... , R-L+1의 값을 더하는 쿼리와 X 위치의 값을 구하는 쿼리를 수행하는 문제입니다. 수열의 범위가 최대 100,000개이며 쿼리의 수가 최대 100,000개이기 때문에 효율적인 자료구조가 필요합니다. 또한, 수행할 쿼리 역시 모든 구간에 동일한 값을 더하는 작업이 아니기에 주어진 수열을 그대로 사용해서는 문제를 해결할 수 없습니다. 문제를 해결하기 위해서는 전처리 과정이 필요합니다. 그럼 어떤 전처리 과정이 필요할까요?

 

문제 해결하기

우리가 작성할 쿼리를 다시 살펴보겠습니다. 첫 번째 쿼리(q=1)는 주어진 구간[L, R]에 값을 증가시키는 쿼리입니다. 구간의 값을 변경하는 효율적인 자료구조는 lazy propegation을 활용한 세그먼트 트리입니다. 하지만 이 방법은 구간에 동일한 값을 더할 때에만 사용할 수 있습니다. 따라서, 우리는 주어진 수열을 전처리 과정을 통해 lazy propegation을 적용할 수 있도록 변경하면 쿼리를 효율적으로 해결할 수 있습니다. 그렇다면 어떻게 변경해야 동일한 값을 더해도 1, 2, ... , (R-L+1)의 값을 더했다는 걸 표현할 수 있을까요? 여기서 우리가 주목할 점은 증가시키는 값이 항상 일정하게 커진다는 점입니다. 일정하게 커지는 값을 더하면 인접한 두 수 사이의 차이값 역시 일정하게 증가하며, 우리는 이 점을 활용할 수 있습니다.

수열 [ 1 2 3 4 5 ]을 예시로 살펴보겠습니다. 기본 수열인 [ 1 2 3 4 5 ]을 인접한 두 수의 차이를 기준으로 표현하면 [ 1 1 1 1 1 ]로 표현할 수 있습니다. 이 상태에서 구간 [ 1:5 ]의 값을 증가하는 쿼리를 적용하면 수열은 [ 2 4 6 8 10 ] 가 되며, 두 수의 차이를 기준으로 표현하면 [ 2 2 2 2 2 ]이 됩니다. 이처럼 증가시키는 값이 일정하게 커지면 해당 구간에 포함된 값들의 차이는 항상 동일하게 커지며, 인접한 두 수의 차이를 기준으로 배열을 만들면 첫 번째 쿼리를 효율적으로 처리할 수 있습니다.

 

두 번째 쿼리(q=2)는 X번째 숫자의 값을 출력하는 쿼리입니다. 만약 우리가 수열을 고치지 않았다면 이 쿼리의 값은 간단하게 구할 수 있습니다. 하지만 우리는 첫 번째 쿼리를 위해 수열의 값을 변경한 상태입니다. 이 상태에서 두 번째 쿼리를 처리할 수 있을까요? 사실 두 번째 쿼리는 우리가 만든 수열의 의미를 생각해보면 쉽게 구할 수 있습니다. 우리가 만든 수열은 인접한 값의 차이를 구한 수열입니다. 따라서, 가장 왼쪽 값부터 X번째 숫자의 차이까지 모두 더하면 우리가 X번째 숫자의 정확한 값을 구할 수 있습니다.

 

지금까지 첫 번째 쿼리와 두 번째 쿼리의 처리 방법을 생각해보았습니다. 이 과정을 통해 우리는 세그먼트 트리의 초깃값은 인접한 숫자들의 차이값을 저장하되, 구간합을 저장하는 세그먼트 트리로 구성하면 된다는 사실을 확인할 수 있습니다. 그리고 첫 번째 쿼리를 처리할 때에는 lazy propegation을 활용하며, 두 번째 쿼리를 처리할 때에는 [ 1:X ]까지의 누적합을 구하면 된다는 알고리즘까지 설계할 수 있었습니다. 알고리즘을 구현한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#define NMAX 100010
typedef long long lint;
 
int N, Q, q, L, R, X;
int inp[NMAX];
 
lint segTree[NMAX*4], lazy[NMAX*4];
 
void updateLazy(int idx, int iL, int iR) {
    segTree[idx] += (lazy[idx]*(iR-iL+1));
    
    if(iL != iR) {
        lazy[idx*2] += lazy[idx];
        lazy[idx*2+1] += lazy[idx];
    }
    
    lazy[idx] = 0;
}
 
void update(int idx, int iL, int iR, int qL, int qR, lint val) {
    if(lazy[idx]) updateLazy(idx, iL, iR);
    
    if(iL>qR or iR<qL) return;
    else if(qL<=iL and iR<=qR) {
        lazy[idx] += val;
        updateLazy(idx, iL, iR);
    }
    else {
        int mid = (iL+iR)/2;
        
        update(idx*2, iL, mid, qL, qR, val);
        update(idx*2+1, mid+1, iR, qL, qR, val);
        
        segTree[idx] = segTree[idx*2] + segTree[idx*2+1];
    }
}
 
lint search(int idx, int iL, int iR, int qL, int qR) {
    if(lazy[idx]) updateLazy(idx, iL, iR);
    
    if(iL>qR or iR<qL) return 0;
    else if(qL<=iL and iR<=qR) return segTree[idx];
    else {
        int mid = (iL+iR)/2;
        
        return search(idx*2, iL, mid, qL, qR) + search(idx*2+1, mid+1, iR, qL, qR);
    }
}
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i]);
        
        // 차이값(inp[i]-inp[i-1])으로 세그먼트 트리 설정
        update(1, 1, N, i, i, inp[i]-inp[i-1]);
    }
    
    scanf("%d", &Q);
    for(int i=1;i<=Q;i++) {
        scanf("%d", &q);
        
        if(q == 1) {
            scanf("%d %d", &L, &R);
            
            // [L, R] 구간 갱신
            update(1, 1, N, L, R, 1);
            
            // (R+1)번째 값 갱신
            if(R+1<=N) update(1, 1, N, R+1, R+1, -(R-L+1));
        }
        else {
            scanf("%d", &X);
            
            printf("%lld\n", search(1, 1, N, 1, X));
        }
        
    }
}
/*
5
1 2 3 4 5
4
1 2 3
1 1 3
2 4
2 3
ans
4
8
*/
 

후기

전처리 과정을 통해 세그먼트 트리를 구현하는 문제입니다. lazy propegation의 개념을 익힐 수 있는 좋은 문제라고 생각하며, 세그먼트 트리는 중급 이상의 난이도를 가진 문제에서 자주 사용되기에 이 문제를 통해 세그먼트 트리와 응용법을 익히는 것을 추천합니다.