Expert스터디 4일차(2016.06.08)

아래 셋은 하는 일이 거의 동일하므로 아무거나 골라 쓰면 됩니다. 개인적으로 Index Tree을 추천합니다.

Fenwick (BIT, Binary Indexed Tree)

https://www.acmicpc.net/blog/view/21

Index Tree (정식 명칭 없음)

int N = 15;
int l = 3;
int r = 8;

int left = N+l;
int right = N+r;
while(left<=right)
{
    if(left&1) printf("include this node");
    if(!(right&1)) printf("include this node");
    left=(left+1)/2;
    right=(right-1)/2;
}

// 위로 올라가기
for(int node = N+index ; node ; node/=2) printf("node : %d\n",node);

Segment tree

https://www.acmicpc.net/blog/view/9

- 문제번호

1. 2042

2. 2934

3. 10999

4. 11658

5. 2243

6. 2336

7. 3653