구간 업데이트와 구간 합이 모두 O(logN)에 가능한 펜윅트리 (Fenwick Tree Lazy Propagation)
(2019.08.11 수정)요즘 이 글의 검색량이 많아져서 조금 수정을 했다. 일반 펜윅트리(Fenwick Tree)에 관한 설명은 어디에나 많이 찾아볼 수 있다.오늘은 구간 업데이트(Range Update)와 구간 합(Range Sum)이 O(lgN)에 가능한 특별한 Fenwick Tree에 대해서 포스팅해볼 것이다. 제목에 Fenwick Tree Lazy Propagation이라 작성했지만실제로 Segment Tree Lazy Propagation처럼 update시에 점만 찍어뒀다가 query시에 한꺼번에 update하는 방식은 아니다.다만 Segment Tree Lazy Propagation처럼 구간합과 구간쿼리가 모두 O(logN)에 가능하다는 뜻으로 썼다. 일반 펜윅트리: https://www...
