바이너리 인덱스 트리 알고리즘 (펜윅 트리) 백준2042

바이너리 인덱스 트리 알고리즘 (Binary Indexed Tree) i&-i 앤드연산을 이용해 누적합을 계산하는 알고리즘이다.

1&-1 : 1

2&-2 : 2

3&-3 : 1

4&-4 : 4

...

 

임을 이용한다. 이렇게 나오는 원리를 알아보면 아래와 같다.

 

i	i 2진수	2의 보수	i&-i	result
1	00000001	11111111	00000001	1
2	00000010	11111110	00000010	2
3	00000011	11111101	00000001	1
4	00000100	11111100	00000100	4

 

1 2 1 4 1 8 1 16 1 32 ...

이렇게 나오는 원리를 이용해 각 인덱스별로 값 1개의 합, 값 2개의 합, 값 1개의 합, 값 4개의 합  구간합을 미리 구해놓는다.

 

백준 2042 구간합구하기

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

 

<풀이>

* update 메소드 :

  배열 초기화 / 값변경 때 바이너리 인덱스 트리를 업데이트 한다.

  중간 변경때는 변경된 차이값 만큼만 update 파라미터로 전달해준다.

* pre_sum 메소드 :

  0부터 현재 인덱스까지의 합을 구한다. N~M 사이 값을 구할땐 pre_sum(M)-pre_sum(N-1) 계산한다. 

 

@@@

public class acmicpc2042 {
    static long[] arr;
    static long[] tree;
    static int N ;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        // 5 2 2
        N = Integer.parseInt(st.nextToken());   // 수의 개수
        int M = Integer.parseInt(st.nextToken());   // 변경이 일어나는 횟수
        int K = Integer.parseInt(st.nextToken());   // 구간 합을 구하는 횟수
        arr = new long[N+1];
        tree = new long[N+1];
 
        // 정수 입력 받기
        long l = 0;
        for (int i = 1; i <= N; i++) {
            l = Long.parseLong(br.readLine());
            arr[i]=l;
            update(i,l);
        }
 
        int a,b;
        long c,diff,result;
        for(int i=0; i<M+K; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Long.parseLong(st.nextToken());
 
            if(a==1){
                diff = c-arr[b];
                arr[b] = c;
                update(b,diff);
            }
            else{
                result = pre_sum((int)c)-pre_sum(b-1);
                System.out.println(result);
            }
        }
    }
 
    private static void update(int i , long l) {
        while(i<=N){
            tree[i] += l;
            i += i&-i;
        }
    }
 
    private static long pre_sum(int end_idx){
        long sum = 0;
        while(0<end_idx){
            sum += tree[end_idx];
            end_idx -= (end_idx&-end_idx);
        }
        return sum;
    }
}