[BOJ/백준] 2042 구간 합 구하기

import math
import sys
input = sys.stdin.readline
def init(node_number,start,end):
    global segement_tree,arr
    if start == end:
        segement_tree[node_number] = arr[start]
        return segement_tree[node_number]
    else:
       segement_tree[node_number] = init(node_number*2, start, (start+end)//2) + init(node_number*2+1, (start+end)//2+1, end)
       return segement_tree[node_number]

def update(node_number,start,end,index,diff):
    global segement_tree
    if (index < start) or (index > end):
        return
    segement_tree[node_number] = segement_tree[node_number] + diff
    if (start != end):
        update( node_number*2, start , (start+end)//2,index,diff)
        update(node_number*2+1, (start+end)//2+1,end,index,diff)

def sum_range(node_number,start,end,left,right):
    global segement_tree
    if (left > end) or (right<start):
        return 0
    if (left <= start) and (end<=right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)

N,M,K = map(int,input().split())
height = math.ceil(math.log2(N))
tree_size = 2**(height+1)-1
segement_tree = [0]*tree_size
arr = [int(input()) for _ in range(N)]

init(1,0,N-1)
cnt = M+K
while cnt:
    command,number1,number2 = map(int,input().split())
    if command == 1:
        diffrence = number2 - arr[number1-1]
        arr[number1 - 1] = number2
        update(1,0,N-1,number1-1,diffrence)
    else:
        print(sum_range(1,0,N-1,number1-1,number2-1))
    cnt -= 1

 

 

세그먼트 트리를 활용한 문제이다.

 

범위의 값을 저장하는 트리를 만들어두는 방식이고, 그걸 통해, 값이 변경 시 반복횟수를 줄이는 방식이다.

 

세그먼트 트리에 대해서 공부하면서 푼 문제라 아직 익숙하지 않다.

 

일단 기억하고 있는 세그먼트 트리의 기준은

 

세그먼트 트리로 만들고 싶은 원본 배열의 길이가 N이라고 할때

 

세그먼트 트리의 길이는 주어진 N보다 크거나 같은 2^k를 구하고, 이것의 2배를 하면 세그먼트 트리의 사이즈가 된다.

 

루트노드는 무조건 1이고,

 

루트노드의 왼쪽 노드는 2, 오른쪽 노드는 3이 된다.

 

 

세그먼트 트리에서 부모노드 A가 있을 때에 

 

A노드의 왼쪽 자식 노드는 A*2의 크기가 되고,

 

오른쪽 자식 노드는 A*2 + 1이 된다.

 

 

그리고 여기서 또 중요한 것은 범위이다.

 

특정 부모노드의 범위가 [left , rigiht] 이라고 할때, 

 

이 부모노드의 왼쪽 자식노드는 [left , (left+right)//2]가 되고

 

오른쪽 자식 노드는 [(left+right)//2 + 1, right] 가 된다.

 

이렇게 만들어주면 세그먼트 트리의 초기화가 가능하다.

 

이렇게 한뒤 특정 값의 갱신은 그 값이 갱신된 위치를 찾아, 그 변화량 만큼 바꿔주면 된다.

 

 

특정 범위 합은 범위를 벗어났을때, 범위안에 완전히 들어왔을때, 범위에 일부분 겹쳤을때로 나뉠수 있다.

 

이걸 이용해서 풀면된다.

 

위와 같이 세그먼트 트리를 위와 같이 주어진 조건에 맞춰서 만들고, 그 범위조차 원리에 맞게 만들어도 되지만, 쉽게 풀기 위하여, N 이 12라고 해도 N이 16일때와 같이 2의 제곱수의 크기만큼의 배열이 있다고 가정하고 만들어도 괜찮다.

 

 

import sys
import math
def init():
    global tree_size

    for i in range(tree_size-1,0,-1):
        segement_tree[i] = segement_tree[i*2] + segement_tree[i*2+1]


def update(index,diff):
    while index >= 1:
        segement_tree[index] += diff
        index//=2

def sum_range(node_number,start,end,left,right):
    if left > end or start > right:
        return 0
    if (left <= start) and (end <= right):
        return segement_tree[node_number]
    return sum_range(node_number*2,start,(start+end)//2,left,right) + sum_range(node_number*2+1,(start+end)//2+1,end,left,right)
input = sys.stdin.readline

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

height = math.ceil(math.log2(N))
tree_size = 2**height
total_size = 2**(height+1)

segement_tree = [0]*total_size

for i in range(N):
    segement_tree[tree_size + i] = int(input())

init()
for i in range(M+K):
    command = list(map(int,input().split()))
    if command[0] == 1:
        diff = command[2] - segement_tree[tree_size + command[1] - 1]
        update(command[1]+tree_size-1,diff)
    else:
        print(sum_range(1,0,tree_size-1,command[1]-1,command[2]-1))

세그먼트 트리 자체를 2의 제곱수의 크기일때로 생각하고  넣어주는 방식으로 푸는 방식이다.