Segment Tree 특정 범위의 Array 의 Sum을 빠르게 하기 위해 만들어진 기법이다. 만약 [3,5,8,1,3,9] 라고 하는 Array가 주어 졌다고 생각해 보자. 이를 Tree로 만들면 다음과 같다. 이 Tree에서 주의해서 봐야할 점은 우측에 '0' 이다. 반듯이 Tree의 Balance를 맞춰줘야 한다. 이렇게 Tree가 만들어지면 다음과 같이 Query가 가능하다. [3,5,8,1,3,9] 에서 0 ~ 5까지의 Sum은? 상기와 같이 Index 0과 5 즉 Left Index < Right Index인 관계에서 Left Index가 짝수이면 상위 노드로 올라간다. Right Index 가 홀수이면 상위 노드로 올라간다 라는 개념을 만들 수 있다. 그런데 상위 노드의 Index는 몇인가..