앞서 Segment Tree를 알아 보았다. 2021.05.02 - [Problem Solving] - Segment Tree 그런데 생각보다 개발량도 많고 필요할때 바로 만들어서 쓴다는게 쉽지 않다. 그래서 Binary Indexed Tree를 알아보고자 한다. Binary Indexed Tree는 크게 2개의 Array가 필요하다. N+1 Size의 오리지널 Array N+1 Size의 Fenwick Tree Array 오리지널 Array는 입력하고자 하는 Array 그 자체라고 생각하면된다. [1,3,5,7,9,11,13,15] 라는 배열이 있다면 이것을 Original Array = [NA,1,3,5,7,9,11,13,15] 로 유지 하는 것이다. NA가 들어가는 이유는 첫번째 Value를 1이라..