구간 합 쿼리

문제 설명

세그먼트 트리를 구현하여 구간 합 쿼리와 점 업데이트를 처리하세요.

연산

• update(i, v): i번째 원소를 v로 변경
• query(l, r): l부터 r까지의 합 반환

입력 형식

첫 줄: N M (원소 수, 쿼리 수)

둘째 줄: N개의 초기 값

다음 M줄: 쿼리 (1 i v: 업데이트, 2 l r: 구간 합)

시간 복잡도

• 빌드: O(N)
• 업데이트: O(log N)
• 쿼리: O(log N)