[백준] 10999번 : 구간 합 구하기2

10999번: 구간 합 구하기 2

10999번: 구간 합 구하기 2

📄 문제개요

구간합을 구하는 문제로, 쿼리와 업데이트가 주어졌을때, 턴마다 결과를 출력하는 문제이다.

🤔 문제분석

구간 업데이트

기존의 구간합 로직으로 구현한다면 시간복잡도는 KlogN이 될것이다. 만약 구간이 엄청 크다면 원하는 시간복잡도안에 문제를 해결 할 수 없습니다.

느리게 갱신되는 세그먼트 트리 (Segment Tree Lazy Propagation)

📝 의사코드

1. 세그먼트 트리를 초기화 한다.
2. 쿼리와 업데이트를 분기한다.

💻 코드

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

tree_size = 4 * N

arr = [int(input()) for _ in range(N)]

tree = [0 for _ in range(tree_size)]
lazy = [0 for _ in range(tree_size)]

def init(start, end, node):
    if start == end:
        tree[node] += arr[start]
    else:
        mid = (start + end) // 2
        init(start, mid, node * 2)
        init(mid+1, end, node * 2 + 1)
        tree[node] = tree[node * 2] + tree[node * 2 + 1]

def update_lazy(start, end, node):
    if lazy[node] != 0:
        tree[node] += lazy[node] * (end - start + 1)
        if start != end:
            lazy[node * 2] += lazy[node]
            lazy[node * 2 + 1] += lazy[node]
        lazy[node] = 0
    
def update(start, end, left, right, node, diff):
    update_lazy(start, end, node)
    if left > end or right < start:
        return
    
    if start >= left and end <= right:
        tree[node] += (end - start + 1) * diff
        if start != end:
            lazy[node * 2] += diff
            lazy[node * 2 + 1] += diff
        return
    mid = ( start + end ) // 2
    update(start, mid, left, right, node * 2, diff)
    update(mid + 1, end, left, right, node * 2 + 1, diff)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]
    
def query(start, end, left, right, node):
    update_lazy(start, end, node)
    if left > end or right < start:
        return 0
    if start >= left and end <= right:
        return tree[node]
    mid = ( start + end ) // 2
    lquery = query(start, mid, left, right, node * 2)
    rquery = query(mid + 1, end, left, right, node * 2 + 1)
    return lquery + rquery
    

init(0, N-1, 1)

for _ in range(M+K):
    temp = list(map(int, input().split()))
    if temp[0] == 1:
        b, c, d = temp[1:]
        update(0, N-1, b-1, c-1, 1, d)
    else:
        b, c = temp[1:]
        print(query(0, N-1, b-1, c-1, 1))

🎯 피드백 및 개선사항

처음문제를 접할때, 어떤식으로 최적화 해야할까 고민중, 생각이 잘 떠올리지 않아 인터넷에 찾아보았습니다.

느리게 갱신되는 세그먼트트리 가있었고 해당부분을 참고하여 새로운 알고리즘을 학습하였습니다.

❓다른사람은 어떻게 풀었을까?

해결해야하는 방법이 정형화 되어있습니다.