(알고리즘) 구간트리(Segmentation Tree)

배열의 크기가 15일 때 구간 트리의 각 노드가 표현하는 각 구간들을 보여준다.
맨 위가 루트가 표현하는 구간이고, 양쪽 아래는 루트의 두 자식 노드들이 표현하는 구간이다. 이때 구간트리는 노드마다 해당 구간에 대한 계산결과를 저장해 둔다. 예를들면 구간의 최소치를 구하는 구간 트리는 해당 구간의 최소치를 각 노드에 저장한다.
예를들어, 구간[6,12]는 세 구간 [6,7] [8,11] [12]의 합집합으로 표현할 수 있다.
각 구간의 최소치는 미리 계산해두었으니 이 셋중의 최소치가 우리가 원하는 답이 된다.
따라서 O(n)대신에 O(lgn)이 될 것이다.



**루트노드를 배열의 1번원소로 ,노드 i의 왼쪽자식은 2*i, 오른쪽 자식은 2*i+1이 된다.
이렇게하면 일차원배열에 간단하게 표현 할 수 있다.
그럼 배열의 길이 n은 얼마로 해야 할까? 배열의 길이 n이 2의 거듭제곱이라면 배열의 길이는 2n이면 충분하다.그러나 n=6인경우는 인덱스의 최대위치가 2n을 초과하는 13이 된다는 사실을 알 수 있따. 배열의 길이를 안전하게 구하려면 가장가까운 2의거듭제곱으로  n을올림한뒤 2를 곱해야 한다. n=6인경우는 거듭제곱은 8이니 배열의 길이를 16으로 ㅎ는 식이다.
귀찮으면 그냥 n에 4를 곱하면 된다.

<구간트리의 초기화>

public class RMQ {

//배열의 크기
private int n;

//해당 노드를 저장하는 배열
int[] rangeMin;
RMQ(int[] array)
{
this.n=array.length;
rangeMin=new int[n*4];
init(array,0,n-1,1);
}
private int init(int[] array, int left, int right, int node) {
// TODO Auto-generated method stub
if(left==right)
return rangeMin[node]=array[left];

int mid=(left+right)/2;
int leftMin=init(array,left,mid,node+1);
int rightMin=init(array,mid+1,right,node+1);

return rangeMin[node]=Math.min(leftMin,rightMin);

}

}


****구간 트리의 질의 처리
private int query(int left,int right)
{
return query(left,right,1,0,n-1);
}
//[left,right]는 찾고자 하는 구간 [nodeLeft,nodeRight]는 현재 노드의 구간 node는 현재 노드
private int query(int left,int right,int node,int nodeLeft,int nodeRight)
{
if(right<nodeLeft || left>nodeRight)return Integer.MAX_VALUE;

if(left<=nodeLeft && right>=nodeRight)return rangeMin[node];

int mid=(nodeLeft+nodeRight)/2;

return Math.min(query(left,right,node*2,nodeLeft,mid),
query(left,right,node*2+1,mid+1,nodeRight));
}



**구간트리의 갱신
--->전처리를 통해 구간 트리를 생성한 다음에 원래 배열의 값이 바뀐다면 어떻게 해야 할까? 원래 배열의 index위치가 newValue로 바뀐다면 이 위치를 포함하는 구간은 트리에 O(logn)개 있을 것이다. 따라서 이들만 재계산하면 O(logn)시간에 구간트리를 갱신 할 수 있을 것이다.

private static int update(int index,int newValue)
{
return update(index,newValue,1,0,n-1);
}
private static int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
// TODO Auto-generated method stub
if(index<nodeLeft || index>nodeRight)
return rangeMin[node];
if(nodeLeft==nodeRight)return rangeMin[node]=newValue;

int mid=(nodeLeft+nodeRight)/2;
return rangeMin[node]=
Math.min(update(index,newValue,node*2,nodeLeft,mid),update(index,newValue,node*2+1,mid+1,nodeRight));

}