세그먼트 트리, 펜윅 트리

세그먼트 트리

세그먼트 트리 = 구간의 어떤 결과를 트리 노드에 저장해놓는 자료구조 형태

 

세그먼트 트리 = 구간 트리 =  꽉 찬 이진 트리

-> 배열로 표현하는 것이 효율적이다.

-> i번째 노드의 왼쪽, 오른쪽 자손은 각각 2*i, 2*i +1이 된다

 

 다양한 형태의 문제를 세그 트리로 풀어나갈 수 있다.

구간의 최소값, 구간의 최대값, 구간 합, 구간의 최소치 두개, 정렬된 배열에서 구간의 최대 출현 빈도

 

구간의 최대 출현 빈도는 노드를 다음과 같이 응용 가능하다.

단순히 왼쪽, 오른쪽 자식의 결과 중 최대값을 취해서 만들 수 있으면 좋겠지만

왼 : {1,1,1,2,2} , 오 : {2,2,3,3,3} 이면 합치는 데에 정보가 더 필요하다.

각 구간의 양쪽 끝 구간의 숫자와 빈도를 같이 저장하여 합치는 데에 사용한다.

 

struct RangeResult {
    int size; // 구간의 크기
    int mostFreq; // 가장 자주 등장하는 숫자의 출현 횟수
    int leftNumber, leftFreq; // 왼쪽 끝 숫자와 출현 횟수
    int rightNumber, rightFreq; // 오른쪽 끝 숫자와 출현 횟수
 }
 
 // 왼쪽 구간 a의 결과와 오른쪽 구간 b의 결과를 합친다.
 RangeResult merge(const RangeResult& a, const RangeResult& b) {
     RangeResult ret;
    
    // 
    
    .. 생략
    // 
 
     return ret;
 }

 

펜윅 트리

펜윅 트리의 자료구조 형태

펜윅트리 = 구간합을 빠르게 구하기 위한 트리 = 부분합을 빠르게 구하기 위한 트리

 

부분합 : 0부터 i까지 합

구간합 : i 부터 j까지 합

 

부분합을 알면 구간합을 알 수 있다. (부분합 j에서 i-1를 빼면 됨)

자신의 길이는 가장 오른쪽 비트부터 1이 처음으로 등장하는 위치의 숫자다

 

부분합 ( 0~i 까지의 합 )

자신의 길이만큼 지워가며 더한다

즉 가장 오른쪽 비트 중 1을 하나씩 0으로 지워가며 더한다

 

pos &= (pos-1) 

1빼면 가장 처음 나오는 1을 0으로 

0이었던 비트를 1로 만들 수 있다. 이걸 &하면 0으로 지우기가 됨

 

ex)

  1000 

&0111    ( 0111 = 1000-1)  

----

0000

 

업데이트

자신의 숫자에 자신의 길이만큼 더하면 부모로 간다.

자신의 길이. 즉 1이 처음 나오는 위치만큼 더하려면 pos & -pos 를 더한다.

x += (x & -x)

 

음수가 2의 보수기 때문. 즉 1의 보수(반전) 에 1을 더하는 것이라서, 올림 받은 첫번째 나온 1보다 큰 위치는 &을 하면 전부 0이됨

 

ex)

1100 이면 100을 더해서 1000 만들기

1110이면 10을 더해서 1100 만들기

 

내가 속한 구간들에 가면서 update가 되는 값인 차잇값을 각 구간에 더해준다. ( diff = val - a[x] )

 

 

초기화 

초기화 과정에서는 차잇값을 더하면 안 된다. 원래 배열의 값을 더해준다. tree[x] += a[i] 

 

 

 

쿼리 시간복잡도는 logn

최악의 경우 트리의 가장 밑바닥을 최대 한번 수행한다

 

업데이트도 마찬가지로 logn  (쿼리 시간복잡도와 같은 이유다)

 

펜윅트리 왜 쓰나요? 그냥 배열로 부분합 저장하면 되는 거 아닌가요

-> 부분합이 중간에 변하는 경우에 단순하게 배열로 저장하게 되면 업데이트에 O(n) 이 걸린다

 

세그트리 쓰면 되는 것 아닌가요?

-> 맞다. 하지만 펜윅 트리가 구현이 더 간단하다. 메모리도 펜윅트리가 덜 쓴다. 세그는 4n, 펜윅은 n

펜윅으로 풀 수 있는 건 세그로도 풀 수 있다. 반대로 세그로 풀 수 있어도 펜윅으로 풀지 못할 수 있다.

 

간단한 펜윅트리 연습 문제

https://leetcode.com/problems/range-sum-query-mutable/description/

 

class NumArray {
public:
    vector<int> tree;
    vector<int> a;
    NumArray(vector<int>& nums) {
        int n = nums.size();
        tree.assign(n+1, 0);
        a.assign(n+1, 0);
        for(int i=0;i<n;i++) {
            a[i+1] = nums[i];
        }

        // 차잇값 고려없이 초기화 한다.
        for(int i=1;i<=n;i++) {
            int x = i;
            while (x < tree.size()) {
                tree[x] += a[i];
                x += (x & -x);
            }
        }
    }
    
    // 차잇값만 업데이트 한다
    void update(int index, int val) {
        int x = index + 1;
        int diff = val - a[x];
        a[x] = val;
        while(x < tree.size()) {
            tree[x] += diff;
            x += (x & -x);
        }
    }
    
    int sumRange(int left, int right) {
        return sum(right+1) - sum(left);
    }

    int sum(int x) {
        int ret = 0;
        while(x > 0) {
            ret += tree[x];
            x &= (x-1);
        }
        return ret;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */