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];