[구름] 잡초 제거.py

import sys
import math
n, q = map(int, sys.stdin.readline().split())
# 잡초
maps = list(map(int, sys.stdin.readline().split()))
# 트리를 위한 배열 크기
# N이 2 * 10**5. log_2(N) = 1 + 5*log_2(2*5)
# print(5 * math.log(10, 2)) = 16.610 정도 된다. 즉 배열 크기는 17은 넘어야 한다
# print(2**17) = 131072, print(2**18) = 262144
# 트리니까 2**18 값에 * 2를 하면 모든 연산값을 담을 수 있는 배열을 만들 수 있다.
Tree = [0 for _ in range(2**19)]

# 트리 생성하기
def init(n, start, end):
	if start == end:
		Tree[n] = maps[start]
		return Tree[n]
	# 트리의 좌측 / 우측의 값을 더한 값이 해당 트리 node의 값
	Tree[n] = init(n*2, start, (start+end)//2) + init(n*2 + 1, ((start+end) // 2) + 1, end)
	return Tree[n]

# 부분합 구하기
# 구하려는 범위는 left - right.
def subSum(node, start, end, left, right):
	# 탐색범위인 start, end가 구하려는 범위 left-right 어디에도 포함이 안 되면 더 이상 구할 필요가 없다
	if left > end or right < start:
		return 0
	# 구하려는 범위 start, end가 탐색범위 left, right에 완전히 포함되면, 더 이상 내려갈 필요가 없다
	if left <= start and end <= right:
		return Tree[node]
	# 왼쪽 노드 / 오른쪽 노드로 나눠 탐색한 값을 반환한다.
	return subSum(node * 2, start, (start+end)//2, left, right) + subSum(node*2 + 1, ((start+end)//2) + 1, end, left, right)

def update(node, start, end, index, value):
	# 바꾸는 숫자의 index값이 탐색 범위 start, end에 포함되지 않을 경우 - 연산할 필요 없다
	if index < start or index > end:
		return
	Tree[node] += value
	# 리프노드에 도달할 때까지, 노드값을 계속 바꾸면서 내려간다
	if start != end:
		update(node*2, start, (start+end)//2, index, value)
		update(node*2 + 1, (start+end)//2 + 1, end, index, value)
	
	
# root node의 index = 1
init(1, 0, len(maps)-1)

for _ in range(q):
	q, a, b = map(int, sys.stdin.readline().split())
	# index 조절
	a -= 1
	
	if q == 1:
		b -= 1
		print(subSum(1, 0, len(maps)-1, a,b))
	elif q == 2:
		update(1, 0, len(maps)-1, a, b)
	elif q == 3:
		update(1, 0, len(maps)-1, a, -b)