문제 링크

https://www.acmicpc.net/problem/2042

문제 설명

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

문제 풀이

첫 시도

def update(start, end, node, idx, diff):
  if start <= idx <= end:
    tree[node] += diff
  if start == end:
    return;
  
  mid = (start + end) // 2
  update(start, mid, node * 2, idx, diff)
  update(mid + 1, end, node * 2 + 1, idx, diff)

시간초과가 나왔다. 다른 함수는 다 제한을 잘 걸었는데 update가 문제인 것 같았다.
곰곰히 생각해보니 tree를 쭈욱 따라 내려가며 update할때 범위를 벗어나면 더 이상 안따라 내려가도 되서 그 노드의 줄기를 짤라버렸다.

두번째 시도

n,m,k = map(int,input().split())

data = []
tree = [-1] * (n * 4)

for _ in range(n):
  data.append(int(input()))

make_tree(0, n-1, 1)
#print(data)
#print(tree)

for _ in range(m+k):
  a, b, c = map(int,input().split())
  if a == 1:
    update(0, n-1, 1, b-1, c - data[b-1])
    data[b-1] = c
  if a == 2:
    print(sum(0, n-1, 1, b-1, c))

시간초과는 해결했지만 틀렸습니다가 떴다,,,
맞왜틀 시전하며 보니 문제 입력에서 b와 c가 index번호가 아닌 몇 번째 번호 였는데, sum에 파라미터를 넣어줄 때 b만 index처리를 해주고 c는 안해줬다.

맞은 코드

def make_tree(start, end, node):
  if start == end:
    tree[node] = data[start]
    return tree[node]
    
  mid = (start + end) // 2
  tree[node] = make_tree(start, mid, node * 2) + make_tree(mid+1, end, node * 2 + 1)
  return tree[node]

def sum(start, end, node, left, right):
  if start > end:
    return 0
  if start > right or end < left:
    return 0
  if start >= left and end <= right:
    return tree[node]
  mid = (start + end) // 2
  return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right)

def update(start, end, node, idx, diff):
  if start > idx or end < idx:
    return;
  if start <= idx <= end:
    tree[node] += diff
  if start == end:
    return;
  
  mid = (start + end) // 2
  update(start, mid, node * 2, idx, diff)
  update(mid + 1, end, node * 2 + 1, idx, diff)

n,m,k = map(int,input().split())

data = []
tree = [-1] * (n * 4)

for _ in range(n):
  data.append(int(input()))

make_tree(0, n-1, 1)
#print(data)	# debugging
#print(tree)

for _ in range(m+k):
  a, b, c = map(int,input().split())
  if a == 1:
    update(0, n-1, 1, b-1, c - data[b-1])
    data[b-1] = c
  if a == 2:
    print(sum(0, n-1, 1, b-1, c-1))
  #print(data)
  #print(tree)

sum, update 과정