[알고리즘] Index Tree

아래 Blog를 공부하면서 공부한 내용을 정리합니다. https://blog.naver.com/ndb796/221312822103

index tree를 알기전에 어떤수의 최하위 비트를 찾는 것을 알아야한다.

#include<stdio.h>

int main(void)
{
    for (int i = 0; i < 17; i++)
    {
        printf("%d숫자는 %d번째가 1이다.\n", i, (i&-i));
    }
    return 0;
}

결과는 아래와 같다.

0숫자는 0번째가 1이다.
1숫자는 1번째가 1이다.
2숫자는 2번째가 1이다.
3숫자는 1번째가 1이다.
4숫자는 4번째가 1이다.
5숫자는 1번째가 1이다.
6숫자는 2번째가 1이다.
7숫자는 1번째가 1이다.
8숫자는 8번째가 1이다.
9숫자는 1번째가 1이다.
10숫자는 2번째가 1이다.
11숫자는 1번째가 1이다.
12숫자는 4번째가 1이다.
13숫자는 1번째가 1이다.
14숫자는 2번째가 1이다.
15숫자는 1번째가 1이다.
16숫자는 16번째가 1이다.
계속하려면 아무 키나 누르십시오 . . .

즉 어떤수의 마지막 비트(1)를 기준으로 Data를 저장한다.

아래와 같이 저장한다.

index 저장Value

)

이렇게 하는 이유는 탐색을 편하게 하기 위해서다.

만일 index 3번이 변경사항이 있다면 3번은 bit로 0011이다. 그다음에 변경하는 아이는 0100이다. 1000이변경되고 그다음은 10000이다.

즉, 1을 하나씩 shift시키면 변경할 아이를 찾기 쉽다. index 3 > 4 > 8 > 16 만 변경하는 것이다.

이걸 code로 하면 다음과 같다. 여기서는 buffer에 구간 합을 넣는다.

추가(2018.9.15)

UPDATE

void update(int index, int value)
{
        while(index<MAXN)
        {
            buffer[index] += value;
            index += (index&-index);
        }
}

Searching

int searching(int index)
{
    int retvalue = 0;

    while(index>0 && MAXN>index)
    {
        retvalue += buffer[index];
        index -= (index&-index);
    }
        return retvalue;
}

solution

#include<stdio.h>

#define MAXN 17

int buffer[MAXN];

void update(int index, int value)
{
    while(index<MAXN)
    {

buffer[index] += value;

        index += (index&-index);
    }

}

int searching(int index)
{

int retvalue = 0;

    while(index>0 && MAXN>index)
    {

retvalue += buffer[index];

        index -= (index&-index);

}

    return retvalue;

}

int searchingRange(int start, int end)
{
    return searching(end) - searching(start - 1);

}

int main(void)
{
    update(1, 1);
    update(2, 2);
    update(3, 3);
    update(4, 4);

update(5, 5);

int sum = 0;

    sum = searching(3);
    sum = searching(2);
    sum = searching(10);
    sum = searching(17);

sum = searching(5);

sum = searchingRange(3, 5);

    return 0;
}