606 세그먼트트리

이진트리여야함
리프노드만 원본
종류

1. 트리의 구간합을 구하는경우
2. 배열을 구간합으로 구하는경우
   • 이때 배열의 각값은 리프노드가된다.
   • 이때 질의 인덱스를 세그먼트 트리인덱스로 바꿔야한다
     • 질의인덱스+ 2^k -1

고로 리프노드 로 트리를 초기화해야함

리프노트로 초기화할때 배열의 크기
리프노드가 N개일 때
$2^k \geq N$
배열의 크기: $2^k*2$

1. start_index % 2== 1일 때 해당 노드를 선택한다. // 자식노드임
2. end_index % 2== 0일 때 해당 노드를 선택한다. //부모노드임
3. start_index depth 변경: start_index = (start_index + 1) / 2 연산을 실행한다. //부모노드로이동
4. end_index depth 변경: end_index = (end_index - 1) / 2 연산을 실행한다. //부모노드로 이동
5. 1~4를 반복하다가 end_index < start_index가 되면 종료한다.

사람들은존나천재가틀림없다.