Baekjoon 1275. 커피숍2 / Python

1275. 커피숍2

난이도 : 골드 1
소요 시간 : 15분
날짜 : 2025.01.08
언어 : 파이썬
알고리즘 유형 : 세그먼트 트리

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 정수배열이 주어진다.
2. x, y, a, b의 쿼리가 주어진다.
3. x~y의 합을 출력하고,
4. a번째 수를 b로 바꾼다.

2. 해결 방식

1. 세그먼트트리 자료구조의 기본적인 문제이다.
   • 세그먼트트리의 생성
   • 세그먼트 트리 누적 합 구하기
   • 세그먼트 트리 갱신

3. 정답 코드

import sys;input = sys.stdin.readline

def make_seg(n, arr):
    seg = [0] * (4 * n)
    def make(node, s, e):
        if s == e:
            seg[node] = arr[s]
            return seg[node]
        mid = (s + e) // 2
        seg[node] = make(node * 2 + 1, s, mid) + make(node * 2 + 2, mid + 1, e)
        return seg[node]
    make(0, 0, n - 1)
    return seg

def find_seg(seg, x, y, node, s, e):
    if x > e or y < s: return 0
    if x <= s and e <= y: return seg[node]
    mid = (s + e) // 2
    return find_seg(seg, x, y, node * 2 + 1, s, mid) + find_seg(seg, x, y, node * 2 + 2, mid + 1, e)

def update_seg(seg, idx, num, node, s, e):
    if s== e:seg[node] = num;return
    mid = (s + e) // 2
    if s <= idx <= mid:
        update_seg(seg, idx, num, node * 2 + 1, s, mid)
    else:
        update_seg(seg, idx, num, node * 2 + 2, mid + 1, e)
    seg[node] = seg[node * 2 + 1] + seg[node * 2 + 2]


if __name__ == '__main__':
    N, Q = map(int, input().split())
    Arr = list(map(int, input().split()))
    seg = make_seg(N, Arr)

    for _ in range(Q):
        X, Y, A, B = map(int, input().split())
        print(find_seg(seg, min(X, Y) - 1, max(X, Y) - 1, 0, 0, N - 1))
        update_seg(seg, A - 1, B, 0, 0, N - 1)