티스토리 뷰

http://jason9319.tistory.com/282 문제를 lazy progatition을 이용한 segment tree를 이용하다가 멘탈이 나가서 fenwick tree를 공부하였다. (https://www.acmicpc.net/board/view/15993)


펜윅트리는 BIT(Binary Indexed Tree)로도 불리며 갱신이 이루어지는 range의 구간 합 연산을 빠르게 해결해주는 자료구조로 알려져있다.


자료구조의 정당성과 시간복잡도등은 https://www.acmicpc.net/blog/view/21에 잘 설명이 되어있고 여기서는 간단하게 사용법만 알아보겠다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll tree[MAX_N+1];
void update(ll x, ll val) {
    while (x <= MAX_N) {
        tree[x] += val;
        x += (x&-x);
    }
}
ll query(int x) {
    ll sum = 0;
    while (x > 0) {
        sum += tree[x];
        x -= (x&-x);
    }
    return sum;
}
cs


세그먼트 트리에 비해 소스코드가 매우 간결하다


업데이트 연산 쿼리 연산 모두 log시간에 해결되며 update(x,val)은 x에 val만큼을 더해주는 연산이며


query(x)는 1~x까지의 구간합을 출력하게 된다.


따라서 x~y까지의 구간합을 구하고 싶을 때 query(y)-query(x-1)을 출력하면 된다.


위의 소스에서 update연산은 한 지점으로의 update 연산만을 가능케하는데


약간의 테크닉을 활용하여 query 함수에 대한 정의를 바꾼다면 구간에 대한 update연산도 log시간에 해결해줄 수 있다.


예를들어 1~N의 range에 x~y까지의 구간에 모두 val씩 업데이트한다고 생각해보자


그렇다면 update(x,val) ,update(y+1,-val)을 이용할 수 있다.


이렇게 업데이트를 할 경우 (int i: x~y) 에 대한 query(i)는 1~i까지의 합을 나타내기 때문에 업데이트 된 x를 가지게 되며 y+1 이상의 수는 x와 -x을 더하게 되어 상쇄되게 된다.


이렇게 구성할 경우 구간에 대한 합연산이 log시간에 처리되며 query(i)는 기존 1~i까지의 합을 나타내는것이 아닌 i위치의 누적합을 출력하게 된다.


1
2
3
4
5
6
7
8
9
void go(ll x, ll y, ll val) {
    if (x <= y)
        update(x, val), update(y + 1-val);    //구간 x~y까지의 업데이트 
    else {
        update(1, val);            //구간 1~x, y~MAX_N까지의 업데이트
        update(x + 1-val);
        update(y, val);
    }
}
cs


'알고리즘 관련 > 알고리즘&이론' 카테고리의 다른 글

(pow(A,B))mod C 를 logB 시간안에 구하는 함수  (0) 2017.06.18
Parallel binary search  (0) 2017.06.14
Fenwick Tree(Binary Indexed Tree)  (3) 2017.06.14
Persistent Segment Tree  (14) 2017.06.05
제1종 스털링 수  (0) 2017.05.29
Minimum Path cover in DAG  (0) 2017.05.29
댓글
  • 프로필사진 SDF 잘 보고 갑니다~
    근데 정말 열심히 하시네요. ㅎㅎ
    2017.08.08 11:56
  • 프로필사진 JASON 자손9319 감사합니다^^ 부족해서 더 열심히 해야할거 같아요ㅎㅎ 2017.08.08 22:25 신고
  • 프로필사진 넘열씨미 열심히 보고 따라해 보고 있는 초짜 입니다. 궁금한 사항이 있어서요.
    백준 2042(구간합구하기1) 문제에 펜윅트리를 적용해보면 결과가 맞는데요.
    백준 10999(구간합구하기2) 문제에 펜윅트리를 적용해 보면 결과가 틀립니다.
    디버깅을 해보면 의도와 다르게 동작을 하네요.
    x ~ y 구간 업데이트할때, update(x,val), update(y+1,-val) 이런 식으로 하면 왜. 틀리게 나오는 걸까요 ?

    java 기준으로 소스 코드는 아래와 같습니다.
    import java.io.*;
    import java.util.*;

    public class FWT_구간합구하기2_boj10999 {
    static int N, M, K;
    static long[] tree;

    public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());

    tree = new long[N+1];

    for(int i=1; i<=N; i++) {
    long val = Long.parseLong(br.readLine());
    update(i, val);
    }

    for(int i=1; i<=(M+K); i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());

    if(a==1) {
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());
    long d = Integer.parseInt(st.nextToken());

    update_range(b, c, d);

    } else {
    int b = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());

    bw.write(sum_range(b, c) + "\n");
    }
    }

    bw.flush();
    }

    static long sum_range(int idx_fr, int idx_to) {
    return sum(idx_to) - sum(idx_fr-1);
    }

    static long sum(int idx) {
    long ans=0;

    while(idx>0) {
    ans += tree[idx];
    idx -= (idx & -idx);
    }

    return ans;
    }

    static void update_range(int idx_fr, int idx_to, long diff) {
    update(idx_fr, diff);
    update(idx_to+1, -diff);
    }

    static void update(int idx, long val) {
    while(idx<=N) {
    tree[idx] += val;
    idx += (idx & -idx);
    }
    }
    }
    2019.08.21 07:14 신고
댓글쓰기 폼