Coding 공부

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 = 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] = 0
init()
for i in range(M):
    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:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]
        print(sum_range(1,0,tree_size-1,command[1]-1,command[2]-1))

세그먼트 트리를 이용해서 풀어야했던 문제이다.

여전히 세그먼트 트리는 정확히 잘 모르겠다는게 함정이지만, 예전에 만들어뒀던 세그먼트 트리에서 일부분만 고쳤다.

구간의 값을 특정위치에 미리 저장을 해놓고, 어떤 위치의 값이 변했을때, 그 값이 포함된 구간들을 갱신하는 것인데,

아직 세그먼트 트리는 어려운 것같다.

세그먼트 트리를 짜놓은 코드를 이용해서, 풀라면 풀수 있을것 같지만, 실전에서 노베이스부터 설계를 하라고 하면

너무 어려울 것 같다.

import sys

input = sys.stdin.readline


def init(N):
    for i in range(N-1,0,-1):
        tree[i] = tree[i<<1] + tree[i<<1|1]

def query(left,right,N):
    ans = 0
    left = left +N
    right = right +N
    while left<right:
        if (left&1):
            ans += tree[left]
            left += 1
        if (right&1):
            right -= 1
            ans += tree[right]
        
        left >>= 1
        right>>= 1
    return ans


def update(pos,val,N):
    tree[pos+N] = val
    pos = pos +N
    while pos > 1:
        tree[pos>>1] = tree[pos] + tree[pos^1]
        pos >>= 1
N,M = map(int,input().split())


tree = [0]*(3*N)


for _ in range(M):
    command = list(map(int,input().split()))
    if command[0] == 1:
        update(command[1],command[2],N)
    else:
        if command[1] > command[2]:
            command[1],command[2] = command[2],command[1]

        sys.stdout.write(str(query(command[1],command[2]+1,N))+'\n')

 이 코드는 https://blog.joonas.io/129 에 있는 비재귀 세그먼트 트리를 설명한 글을 이용해서 푼 문제이다.

여전히 어렵다. 

업데이트가 빈번하고, 특정값을 구할때, 트리를 이용한 풀이들이 많은데, 아직 트리에 대해 정확히 알지 못해서

그런지 많이 어렵다.

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:
        mid = (start+end)//2
        segement_tree[node_number] = min(init(node_number*2, start, mid) , init(node_number*2+1, mid+1, end))
        return segement_tree[node_number]

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

N,M = map(int,input().split())
INF = float('inf')
segement_tree = [-1]*(N*4+20)
arr = [int(input()) for _ in range(N)]
init(1,0,N-1)

for _ in range(M):
    left,right = map(int,input().split())
    print(find_min_number(1,0,N-1,left-1,right-1))

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의 제곱수의 크기일때로 생각하고  넣어주는 방식으로 푸는 방식이다.