인덱스 트리

일정 데이터 집합에 대하여 구간별로 특정한 데이터를 저장해둔 것을 인덱스 트리라 한다. 

특정 값은 주로 최대값이나 최소값을 의미한다. 위 자료구조를 통해 주로 Min Max Tree를 만든다. 만드는데 시간이 상당히 오래 걸리며 한 번에 깔끔히 완성하는 것은 상당히 어렵다.

BIT에서 해결하지 못했던 최대 최소 문제를 해결해줄 수 있는 알고리즘이긴 하지만... 구현하는데 시간이 오래걸리는 것은 아쉽다.

int tree[20][100000]; void update(int height, int piv, int data){ if(height==18) return; if(tree[height][piv] < data){ tree[height][piv] = data; update(height+1, piv/2, data); return; } } int myPow(int height){ int ret=1; for(int i=0; i<height; i++){ ret*=2; } return ret; } int findMax(int height, int piv, int from, int to){ int range=myPow(height)-1; if(from > to) return 0; int hereFrom = myPow(height)*piv; int hereTo = myPow(height)*piv+range; if(hereFrom==from && hereTo==to) return tree[height][piv]; if(hereFrom>to || hereFrom+range < from) return 0; return max(findMax(height-1, piv*2, from, min(to, hereFrom+myPow(height-1)-1)), findMax(height-1, piv*2+1, max(from, hereFrom+myPow(height-1)), to)); }