catniz   7년 전

식물이 L부터 R까지 자란 것을 1차원 배열에 L부터 R까지 +1을 하여 표시하면 겹치는 식물의 개수를 한 번에 알 수 있는 것을 이용해 푼다는 것을 질문 검색을 통해 알았습니다.

근데 위와 같이 특정 구간을 +1씩 증가시키는 것을 펜윅트리로 구현한다고 하더라고요.

L에서의 값을 +1 하면 L+1, L+2, .. 의 값도 다 +1씩 증가 된다고하는데,

만약 5에서의 값을 +1 하면 6, 8, 16, 32, .... 의 값만 증가되는 것이 아닌가요? 7, 9, 10, 11...등은 값에 변화가 없을 것 같습니다.

혹시 제가 잘못알고있는 것이 있다면 지적해주세요 ㅜㅜ...

잘못알고있는 것이 아니라면 어떻게 펜윅트리로 구현하는지 조언 부탁드립니다.

sksdong1   7년 전

펜윅트리를 다시 공부하셔야 될거 같네요

6 8 16 32만 값이 증가되는거 맞습니다.

근데 7을 구할 때 과정을 보면  (1,2,3,4) , (5,6) , 7  의 범위를 모두 합하게 되는 구조이기 때문에 (펜윅트리 pos-=(pos&-pos))

결국 7을 더할 때 5-6이 더해지면서 6에서 갱신된 1값이 7에도 영향을 줍니다

catniz   7년 전

엌ㅋㅋㅋㅋㅋㅋ맞네요! 제가 업데이트랑 저장하는 것만 생각하고 값을 구하는 방식은 생각을 안했네요!


감사합니다!!

댓글을 작성하려면 로그인해야 합니다.