알고리즘||코딩테스트/백준
[백준 1275번] 커피숍2 - Python
째로스
2023. 7. 10. 10:17
https://www.acmicpc.net/problem/1275
1275번: 커피숍2
첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합
www.acmicpc.net
풀이
사용한 알고리즘 : BIT(Binary Index Tree, segment tree)
풀이 전략
바이너리 인덱스 트리에 대한 이해가 있어야만 풀 수 있는 문제이다.
바로 전에 풀었던 구간합 구하기와 풀이 방법이 동일했다.
바이너리 인덱스 트리와 풀이 방법에 대해 자세히 적어놓았으니 아래 링크를 참고바란다.
https://chaechaeros.tistory.com/106
[백준 2042번] 구간 합 구하기 - Python
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을
chaechaeros.tistory.com
제출코드
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