[백준] 2042번 - 구간 합 구하기 (파이썬)

https://www.acmicpc.net/problem/2042

# 구간 합 구하기
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())

arr = [0]
for _ in range(N):
    arr.append(int(input()))
tree = [0] * (N+1)


def update(i, diff):
    while i <= N:
        tree[i] += diff
        i += (i & -i)


def fromOne_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        i -= (i & -i)
    return result


def print_sum(start, end):
    print(fromOne_sum(end) - fromOne_sum(start-1))


for i, x in enumerate(arr):
    if i > 0:
        update(i, x)

for _ in range(M+K):
    type, a, b = map(int, input().split())
    if type == 1:
        diff = b - arr[a]
        update(a, diff)
        arr[a] = b
    else:
        print_sum(a, b)

 

자료구조, 펜윅트리

1. 입력을 받고 트리를 정의해준다

2. arr의 인덱스와 값을 이용해서 트리를 업데이트해준다 (update)

    - 트리의 인덱스(i)를 diff로 업데이트

    - 2진수의 특성을 이용해서 i에 다음 인덱스를 지정

3. 입력을 받는다

   - 1일 경우 해당 인덱스의 값을 두 값의 차이만큼 더해준다 update(a, dff)

    - 2일 경우 해당 구간의 합을 출력해준다 print_sum(start, end)

    - fromOne_sum : 인덱스 1부터 해당 인덱스 값까지의 합 리턴

 

i & -i는 해당 인덱스(2진수)의 양의 값과 음의 값(2의 보수)을 비트 연산자(&)를 사용하여

0이 아닌 가장 마지막 비트의 값을 나타낼 수 있다.

0 = 0000 = 0

1 = 0001 = 1

2 = 0010 = 2

3 = 0011 = 1

4 = 0100 = 4

이런 식으로 진행을 하며 해당 인덱스에 해당 인덱스 값까지의 합을 저장해서 관리할 수 있다.