백준#11659 - 구간 합 구하기

한음·2022년 3월 10일
0

문제 보기

세그먼트 트리 사용.
리프노드 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))


profile
https://github.com/0hhanum

0개의 댓글