Algorithm/세그먼트트리

백준 2042 구간합구하기 c++ // 펜윅트리 구현방법

https://www.acmicpc.net/problem/2042 1. 구간합배열 vs 펜윅트리수정이 많다면 펜윅트리를 사용해야한다! 2. 펜윅트리 구현방법1. 삽입 : (idx, diff)a[9] : 6을 9로 바꿈 -> 차이인 "3" 만큼을 내려가면서(부모노드에) 갱신시켜줘야함! //원본값 9가 아님에 주의!부모노드의 idx는 어케얻음? -> 9(1001) -> 10(1010) -> 12(1100) -> 16(10000)즉, 본인 idx에서 최하위 비트(1)을 더해주면 부모노드의 idx가 나온다! //1001(9) + 0001 == 1010(10) ... 2. 누적합구하기퍼랭이들을 더해야하는데7에서 시작해서 다음퍼랭이 idx를 얻어내면된다.0111(7) -> 0110(6)->0100(4)즉, 최하의1..