2024 구간 합 구하기 python

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

2042번: 구간 합 구하기

 

 

 

 

문제 접근

세그먼트 트리로 쉽게 풀렸다.

구간 합을 세그먼트 트리의 각 노드에 적으면서 올라가면 쉽게 풀린다.

 

 

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
1. 
"""

N, M, K = map(int, input().split())
node = 2**math.ceil(math.log2(N))
tree = [0 for i in range(node * 2 + 1)]
a, b, c = 0, 0, 0

for n in range(N):
  tree[node + n] = int(input())


def init(index):
  if index >= node:
    return tree[index]

  tree[index] = init(index * 2) + init(index * 2 + 1)
  return tree[index]


def update(index):
  tree[index] = c
  while index > 1:
    tree[index // 2] = tree[index] + (tree[index + 1] if index %
                                      2 == 0 else tree[index - 1])
    index = index // 2


def ans(start, end, index):
  if end < b or start > c:
    return 0
  if b<= start and end <= c:
    return tree[index]
    
  mid = (start + end) // 2
  return ans(start, mid, index * 2) + ans(mid + 1, end, index * 2 + 1)

init(1)
for _ in range(M + K):
  a, b, c = map(int, input().split())
  if a == 1:
    b = b + node - 1
    update(b)
  else:
    print(ans(1, node, 1))