[알고리즘] Segment Tree

Segment Tree

다음을 참고하여 작성하였습니다.

https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221282210534&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=false&from=postView

index Tree의 핵심은 bit연산을 한다는 것이다. 탐색을 위해서는 bit의 마지막 bit의 수를 이용하여 이동하면서 찾는 것이고

segment Tree는 완전 Tree를 이용하여 탐색하는데 우선 순위 Queue와 유사하다고 생각된다.

여기서 핵심은 탐색을 어떻게하느냐 인데 정점 buffer index 1에서 출발하여 하위로 내려가는 방식을 사용한다.

참고로 index Tree는 바닥에서 위로 올라간다.

탐색 부분

currentIndex*2 부분이 핵심이다.

// currentIndex =1에서 부터 시작이다.
// 위에서 부터 출발이다.
int Searching(int start, int end, int currentIndex, int left, int right)
{
    if (left > end || right < start) return 0;
    else if (left <= start && end <= right) return buffer[currentIndex];

    int mid = (start + end) / 2;

    return Searching(start, mid, currentIndex*2, left, right) + Searching(mid + 1, end, currentIndex*2+1, left, right);
}

solution

    #include<stdio.h>

    #define MAXN 16

    #define BASE 7

    int buffer[MAXN];

    void update(int index, int value)
    {    
        buffer[BASE + index] = value;

        int currentIndex = BASE + index;

        do
        {
            int parent = (currentIndex) / 2;
            int anotherIndex = 0;

            if (currentIndex % 2)// 홀수
            {
                anotherIndex = currentIndex -1;
            }
            else
            {
                //짝수
                anotherIndex = currentIndex + 1;
            }

            buffer[parent] = buffer[anotherIndex] + buffer[currentIndex];

            currentIndex = parent;
        } while (currentIndex>1);
    }

    // currentIndex =1에서 부터 시작이다.
    // 위에서 부터 출발이다.

    int Searching(int start, int end, int currentIndex, int left, int right)
    {
        if (left > end || right < start) return 0;
        else if (left <= start && end <= right) return buffer[currentIndex];

        int mid = (start + end) / 2;

        return Searching(start, mid, currentIndex*2, left, right) + Searching(mid + 1, end, currentIndex*2+1, left, right);
    }

    int main(void)
    {

        update(1, 1);
        update(2, 2);
        update(3, 3);
        update(4, 4);
        update(5, 5);

        int sum = 0;

        sum = Searching(1, 8, 1, 1, 8);
        sum = Searching(1, 8, 1, 2, 8);
        sum = Searching(1, 8, 1, 3, 8);
        sum = Searching(1, 8, 1, 3, 4);
        sum = Searching(1, 8, 1, 2, 4);

        update(2, -2);

        return 0;
    }