[Python] 구름. 잡초 제거

https://level.goorm.io/exam/51351/%EC%9E%A1%EC%B4%88-%EC%A0%9C%EA%B1%B0/quiz/1

구름LEVEL

Segment Tree라는 개념을 처음 알게 된 문제.

Segment Tree 개념을 쉽게 설명한 포스트는 아래와 같다. 

https://www.crocus.co.kr/648

세그먼트 트리(Segment Tree)

 

Python 코드는 아래 포스트를 참고해서 만들었다.

 

https://upcount.tistory.com/12

백준 2042번 구간 합 (Python)

 

	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)

view raw [구름] 잡초 제거.py hosted with ❤ by GitHub