ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 펜윅트리
    Algorithm/세그먼트, 펜윅트리 2020. 3. 5. 01:56
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    //펜윅 트리의 완전한 구현
     
    //펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을
    //빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 
    //원소가 전부 0이라고 생각한다
     
    struct FenwickTree
    {
        vector<int> tree;
        FenwickTree(int n) : tree(n+1) {}
        //A[0...pos]의 부분 합을 구한다.
        int sum(int pos)
        {
            //인덱스가 1부터 시작한다고 생각하자.
            ++pos;
            int ret = 0;
            while(pos > 0)
            {
                ret += tree[pos];
                //다음 구간을 찾기 위해 최종 비트를 지운다.                        
                pos &= (pos-1);
            }
            return ret;
        }
        //A[pos]에 val을 더한다
        void add(int pos, int val)
        {
            //인덱스가 1부터 시작한다고 생각하자.
            ++pos;
            while(pos < tree.size())
            {
                tree[pos] += val;
                pos += (pos & -pos);
            }
        }
    };
    cs

     

     

     

     

     

     

    펜윅트리

    부분 합을 이용해 구간 합을 구하는 트리

    박스 안의 숫자는 index이고, 밑의 조그만 숫자는 해당 index를 2진수로 표현한 것입니다.

    tree[i] : 위 그림에서 index가 i인 부분의 합

     

    가상의 A[] 배열의 구간합 [0...pos]를 구하기 위해선

    pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종 비트를 계속지워 나가며 구해지는 박스들을 모두 더하면 됩니다.(pos + 1은 1번부터 시작하기 때문입니다.)

     

    펜윅트리를 갱신하기 위해선

    pos + 1 의 index를 가지는 박스를 찾은다음, pos + 1의 최종비트를 계속 더해 만나는 박스들에 새로운 값을 갱신해 주면 됩니다.

     

     

     

     

     

     

    시간복잡도

    sum : O(lgn)

    add : O(lgn)

     

     

     

     

     

     

    종만북2

    'Algorithm > 세그먼트, 펜윅트리' 카테고리의 다른 글

    Segment with Lazy Propagation  (0) 2020.04.06
    Segment Tree  (0) 2020.03.13

    댓글

Designed by Tistory.