071 : 구간 합 구하기 3

size는 총 2번을 커버해야 한다

- bottomline의 수들과

- 그 수들의 합을 계산할 수 있는 slot들

 

"1에서 다시 2배씩 현재 수까지 도달하는 로직"

> 현재 수가 1이 될때까지 exp /= 2; 하는동안 counter(exponent)를 1씩 올린다면, 총 2회가 나옴

> 그런데 5~7 사이의 수라면 감가된것이 있으므로 exp + 1;

> bottom에서 위로 올라가면서 계산하는 slot을 위해 다시 (exp+1) + 1

  

 

 

 

5는 사실 8에 귀속되어야 하지만,

 

몫을 나눠서 height를 구하는 방식은 4에 귀속 됨

 

즉 4까지 8을 사용하는 것

 

2^3은 8, 그리고 bottom 한줄은 나머지 층수의 모든 노드 수와 동일함

 

 

 

 

기수와 서수 차이

 

 

 

 

 

 

 

15부터 역순으로 1까지

 

그러나 3과 2로 계산되어 1에 더해지므로

 

1 자체는 생각할 필요 없이 2까지만 순회하면 알아서 채워진다

 

 

 

 

 

val이 초기 TP[pointer]보다 크다는 위상의 반쪽만 생각해주면 diff는 

- 양수를 더한다

- 음수를 더한다

connected 된다고 생각하고 무시해도 알아서 해결됨

 

*위와 달리 1 pointer까지 작업해줘야함

 

 

 

 

 

기수 서수 주의할 것

 

 

 

 

 

특정 노드의 자식쌍 L R 이 모두 범위에 들어오면 해당 노드(부모)만 plate에 넣으면 된다. 합 segmentTree이므로

 

그런데 s는 왼쪽끝 경계이고 s 오른쪽 segment Lock하므로

s가 홀수(오른쪽)인경우 해당 R을 개별로 넣고 완전쌍을 구간으로 넣을 수 있도록 오른쪽 한칸 이동한다

 

e도 마찬가지

 

그런데 마지막은 어떻게 되는가?

 

꼭대기 pointer는 1이고 s==e이나

s만 작동하게 됨