구간합 펜윅트리의 업데이트 시간복잡도는 O(logN)이고, 부분구간 갱신이 들어가도 Lazy Propagation 알고리즘으로 O( (logN)^2 )이 걸리게 됩니다.

업데이트의 횟수가 어지간히 많아도 커버될 정도죠

좀 더 구체적인 상황을 얘기해주시면 이해가 더 잘될것 같습니다.

펜윅 트리를 사용하는 것이 가능한 경우라면 펜윅 트리가 더 빠를겁니다.

둘 다 사용하는 것이 가능하다면, 구간 트리(보통 프로그래밍 대회에서 통용되는 Segment Tree...등으로 불리는 것들)가 펜윅 트리보다 Order가 더 낮은 경우를 본 적이 없네요(아마 없을 듯 싶습니다. 펜윅 트리의 모티브가 구간 트리이고, 그 구조를 따르니까요. 구간 트리는 펜윅의 상위 호환일 것 같네요).

게다가 보통 구간 트리는 재귀로, 펜윅 트리는 비트 마스크로 구현하기 때문에, 펜윅으로 가능하면 그리 함이 더 빠를 것 같습니다.

@pl0892029 @chan4928 님 너무감사합니다 좀더 공부해보겠습니다!!