BOJ) 2900. 프로그램

문제:

창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다.

1 2 3 4 5 6 7

void something(int jump) {     int i = 0;     while (i < N) {         a[i] = a[i] + 1;         i = i + jump;     } }

창영이는 함수를 K번 호출하려고 한다. 각각 호출할 때, 인자로 넘기는 jump의 값은 X1, X2, X3, ... Xk 순서이다.

이렇게 호출한 뒤에는 배열의 값이 정상적으로 들어갔는지를 확인하려고 한다. 확인은 총 Q번 하고, 매번 확인을 할 때마다 L과 R(L ≤ R)을 정한뒤, 그 구간의 배열의 합을 구한다. 즉, a[L] + a[L+1] + ... + a[R]을 구한다.

함수를 호출할 때 필요한 X의 값과 창영이가 확인한 횟수 Q가 주어졌을 때, 확인한 결과(배열의 합)을 구하는 프로그램을 작성하시오.

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

해설:

프로그램이 뭐하는 애 인지 생각해보면

배열에서 jump만큼 건너뛰면서 1만큼 더 증가되는 숫자를 넣는 것이다. 

만약 subarray를 이용하여 값을 출력할 경우, 배열크기가 100만이고, 확인하는 횟수가 100만이기 때문에 TLE를 받게 된다.

이 현상을 해결하기 위해 팬윅 트리를 이용하면 매우 빠르게 L부터 R까지 더한 값을 빠르게 확인 할 수 있다.

팬윅 트리에 대한 내용은 여기에 잘 설명되어 있다.

출처: https://www.acmicpc.net/blog/view/21

subsum에 대해 다음과 같은 numbering을 할 경우

L[i] = i & -i 가 된다. L[i]는 이진수로 나타냈을 때 마지막 1이 나타내는 값을 뜻한다.

이럴 경우 A[1] + ... + A[13]을 구할 경우

Tree[1101] + Tree[1100] + Tree[1000],

즉 Tree에서 numbering된 값인

T[13] + T[12] + T[8]가 되고, A[1] ~ A[13]에 해당하는 subsum을 구할 수 있는 것이다

코드:

#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
using namespace std;

vector <long long> tree(1000005);
map<int, long long> m;

long long sum(int i){
        long long ans = 0;
        while( i > 0) {
                ans += tree[i];
                i -= (i & -i);
        }
        return ans;
}

void update(int i, long long num){
        while( i<=1000005) {
                tree[i] += num;
                i += (i & -i);
        }
}

int main(){
        int N, K; cin>>N>>K;
        while(K--){
                int jump;
                scanf("%d",&jump);
                m[jump]++;
        }

        map<int,long long>::iterator iter;
        for(iter=m.begin(); iter!=m.end(); iter++){
                for(int j=1; j<=N; j+=iter->first)
                        update(j, iter->second);
        }

        int Q; cin>>Q;
        while(Q--){
                int L, R; scanf("%d %d",&L,&R);
                printf("%lld\n", sum(R+1) - sum(L));
        }
}