세그먼트 트리 사용.
리프노드 N 개로 perfect binary tree 구성하려면 전체 노드의 개수는
전체 노드 최대 개수 (이진트리) = 2 ^ (height + 1) - 1
height = ceil(log2(N))
= 2 ^ (ceil(log2(N)) + 1) - 1
메모리가 허용될 때는 리프노드 크기 * 4
사이즈로 트리 만든 후 진행해도 무방하다.
import sys
N, M = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))
nums.insert(0, 0) # 노드 번호와 인덱스 일치시키기
intervals = []
tree = [0 for _ in range(262145)] # 트리 구성
def init(start, end, index):
if start == end:
tree[index] = nums[start]
return tree[index]
else:
mid = (start + end) // 2
tree[index] = init(start, mid, index * 2) + init(mid + 1, end, index * 2 + 1)
return tree[index]
def query(start, end, l, r, index):
if (l > end) or (r < start):
return 0
if start >= l and end <= r:
return tree[index]
mid = (start + end) // 2
return query(start, mid, l, r, index * 2) + query(mid + 1, end, l, r, index * 2 + 1)
init(1, N, 1)
for _ in range(M):
l, r = map(int, sys.stdin.readline().strip().split())
print(query(1, N, l, r, 1))