뭐 인덱스트리의 기본적인 알고리즘은 스킵하도록 하고... 나중에 시간 있으면 알고리즘 강좌 올리면서 같이 올리던지...
보통 구현을 할때 바이너리트리로 구현을 하는데 구현하는게 해보면 꾀 귀찮고 추가메모리도 꾀 많이 잡아먹습니다 -.-;
여기 추가메모리를 전혀 사용하지 않고 바이너리인덱스트리보다 훨씬 빠르게 구현할수 있는 방법이 있습니다 !!
대충 구조를 그려보면 이렇습니다. 척 보기에도 트리가 훨씬 간결해 졌군요
잘 보시면 범위의 끝값(ex:1~8의 8)은 유일합니다. 그러므로 추가메모리가 들지 않죠..
Sum indexed-tree를 만들때 왼쪽과 오른쪽 모두 저장할 필요가 없다는 점에서 착안됀 것입니다. 3~4는 1~4에서 1~2를 빼면 돼니까요.
1~k 까지의 합을 구할려면 같은 높이의 왼쪽에 노드들을 모두 더하기만 하면 됍니다.
구현방법에는 아주 기가 막힌 방법이 있더군요...
이 알고리즘과 소스의
제공자는 "
김원재"군(
Arubirate) 이라고 밝힙니다...
void update(int val, int ix) { // ix에 val이 더한다
do {
tree[ix] += val;
ix += ix&(-ix); // add least-sig one
} while(ix<=N);
}
int get_sum(int ix) { // 1~ix에 있는 합을 구한다
int res = tree[0];
while(ix>0) {
res += tree[ix];
ix &= (ix-1); // remove least-sig one
}
return res;
}
멋지지 않은가!! 아주 간단한 방법으로 구현시켰다..
저기 ix 의 변화부분에 대해 간략히 설명하자면
ix & (-ix)는 ix를 이진수로 표현했을때 마지막으로 나오는 1을 뽑습니다.
(6(110) 의 경우 2(010) ) 그리고 이 값을 더하면 트리의 위로 올라갑니다.
ix & (ix-1)은 마지막으로 나오는 1을 지웁니다 ( 6(110)의 경우 4(100) )
뭐 직접 계산해보는게 좋을것 같군요...
(전 소스만 보고 이 과정을 연구한다고 죽는줄 ㅜㅜ)
이걸 응용하면 2차원의 인덱스트리도 빠르게 구할 수 있습니다
참고로 "김원재"군(Arubirate)은 이걸로 ioi기출문제이기도 한 pku1195 모바일을 6위로 풀어내었다고 합니다... 원본을 보고 싶으신분도 여기 들어가보시길...
Trackback Address :: http://isair.silpir.net/trackback/18
2
28258
