[Python]바이너리 인덱스 트리(Binary Indexed Tree)

: 2진법 인덱스 구조를 통해 구간 합 문제 효과적으로 해결가능한 자료구조 
 
(1) 정수에 따른 2진수 표기 

7 => 00000000 00000000 00000000 00000111
-7 => 111111111 111111111 111111111 11111001
7 & (-7) = 1 : 7의 마지막 1의 위치

=> 특정 수 K의 마지막 1의 위치 

유튜브 : 동빈나  <자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복> 캡쳐본

 
(2) 트리 구조 만들기
: 마지막 1의 위치 = 내가 저장하고 있는 값들의 갯수
ex) 16의 0이 아닌 마지막 비트 = 16 
: 1~16까지의 모든 데이터들의 합을 담겠다

유튜브 : 동빈나  <자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복> 캡쳐본

 
(3) 특정 값 변경하기 (처음에 데이터 값 설정할때도 포함)
: 0이 아닌 마지막 비트만큼 더하면서 구간들의 값 변경

유튜브 : 동빈나  <자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복> 캡쳐본

(4) 합 구하기 (1부터 N번째까지의 합 구하기)
: 0이 아닌 마지막 비트만큼 빼면서 구간들의 값의 합 계산

유튜브 : 동빈나  <자료구조: 바이너리 인덱스 트리(Binary Indexed Tree, BIT, 펜윅 트리) 10분 정복> 캡쳐본

 
(5) A~B번째까지의 합 구하기
: (4) 과정에서 N=B인 경우에서 N=A-1인 경우 결괏값을 뺀다 

import sys
input = sys.stdin.readline

#데이터의 갯수, 데이터 변경횟수, 구간합 구하는 횟수
N,M,K =map(int, input().split())

arr=[0]*(N+1)
prefix_sum=[0]*(N+1)

ans_sum=[]

def update(idx, num):
   
    while(idx<=N):
        prefix_sum[idx] += num
        idx += idx &(-idx)

#1번째부터 idx번째까지의 수의 합을 구하는 함수
def sum(idx):
    result =0
    while(idx>0):
        result+=prefix_sum[idx]
        idx-=(idx&(-idx))

    return result
    
def interval_sum(start,end):
    return sum(end)-sum(start-1)
    

#데이터 값 할당하는 초기단계
for i in range(1, N+1):
    data = int(input())
    arr[i]=data
    update(i, data)


for i in range(M+K):
    a,b,c = map(int, input().split())
    if(a==1):
        update(b, c-arr[b])
        arr[b]=c
    else:
        ans_sum.append(interval_sum(b,c))

for i in ans_sum:
    print(i)