세그먼트 트리

 

원리	방향	방법
N개의 배열값들 트리 최하부 리프단 오른쪽 절반에 몰아넣는다	A[2^k] ~ A[2^(k+1) -1]
0 ~ 2^(k-1) 구간인 위로 올라가면서 값을 저장, 요구하는 값을 편하게 load 가능	2N, 2N+1 > 부모인 N에 저장
자식 노드 2쌍이 부모 노드의 값에 영향을 미치는 구조	구간값 계산시 start가 왼쪽 리프쌍에 위치한다면, 부모 노드는 해당 자식 노드값을 포함되므로 선택하지 않는다 end index가 오른쪽 리프쌍에 위치한다면, 부모 노드는 자식 노드값을 포함하므로 선택하지 않는다	start / 2 == 1 > 선택 end / 2 == 0 > 선택
부모 노드로 이동하면서 선택한 것 누적 계산하기	start는 오른쪽 위 부모노드로 end는 왼쪽 위 부모노드로	start = (start+1) / 2 end = (end-1) / 2
새 자식 노드가 하나만 구성되어 더 이상 부모 노드로 이동할 수 없을 때 합산이 종료된다	start와 end가 교차되면 값 종료	end < start

tree상의 index = (기존index) + 2^k - 1

*기존 index는 1부터 시작

 

int treeHeight = 0;
int length = N;
while (length != 0) {
    length /= 2;
    treeHeight++;
}

*주의 : length /= 2 는 2로 나눈 몫 보다는, 다음 번의 length는 이번 length를 반으로 나눈다는 뉘앙스

*주의 : 트리 배열은 우측 반쪽이 N의 공간이며, 트리 자체는 최하단 리프 우측 반쪽이 아닌 최하단 전부를 공간으로 사용하고 있다

 

-

트리 모양을 생각하되

최하단 리프 전체에 N이 들어가 있는 부분을 생각

 

- 

그리고 아래에서 위로 움직이면서 높이를 계산할 것이다

 

-

N을 2로 나눌 수 있으면

트리에서 한 칸 씩 올라갈 수 있다는 말이고 높이가 1씩 더해진다는 것

 

- 

이제부터 세밀한 부분

for 문에서 tree[i] 등을 projecting 하는 범위에서, < 이냐 <=, 0부터 시작하느냐 1부터 시작하느냐를 날카롭게 구분하는 법은 

어디서 시작하고 어디서 끝나는지, 그 influx structure 의 point를 잘 관찰하는 것에 달려있음

 

-

최하단 공간은 

N 뿐 아니라 N+a = 2^?로 나오도록 보정되어 있다

 

-

직전 length 값이 2 이상 4 미만이라 몫이 1이 되면

마지막에 노드, 즉 부모 노드에 도달했다는 뜻이므로 높이 계산은 종료된다

그런데 length가 0이 될때 종료이므로, 높이 하나의 단위를 더 가져간다

 

- 

맨 

 

int treeSize = (int) Math.pow(2, treeHeight + 1);
int leftNodeStartIndex = treeSize / 2 - 1;
MOD = 1000000007;
tree = new long[treeSize + 1];