[백준 1275번] 커피숍2 - Python

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

1275번: 커피숍2

 

풀이

사용한 알고리즘 : BIT(Binary Index Tree, segment tree)

 

풀이 전략

 

바이너리 인덱스 트리에 대한 이해가 있어야만 풀 수 있는 문제이다.

 

바로 전에 풀었던 구간합 구하기와 풀이 방법이 동일했다.

바이너리 인덱스 트리와 풀이 방법에 대해 자세히 적어놓았으니 아래 링크를 참고바란다.

 

https://chaechaeros.tistory.com/106

[백준 2042번] 구간 합 구하기 - Python

 

제출코드

import sys

input = sys.stdin.readline

def prefix_sum(x):
    sum=0
    while x>0:
        sum+=tree[x]
        x-=(x&(-x))
    return sum

def update(x,val):
    while(x<=n):
        tree[x]+=val
        x+=(x&(-x))

def interval_sum(start,end):
    return prefix_sum(end)-prefix_sum(start-1)

n,q=map(int,input().split())

arr=[0]
tree=[0]*(n+1)

temp=list(map(int,input().split()))
arr.extend(temp)

for i in range(1,n+1):
    update(i,arr[i])

for i in range(q):
    x,y,a,b=map(int,input().split())
    if x>y:
        x,y=y,x
    print(interval_sum(x,y))
    update(a, b - arr[a])
    arr[a] = b