구간 트리. [2042]

[1. 문제 설명]

N 개의 수가 주어진다.

특정 위치의 값의 변경이 M 번 발생한다.

특정 구간의 합을 K 번 해야 한다.

=> 수열의 값이 변할 수 있을 때, 특정 구간의 합을 계산한다.

[2. 풀이 접근]

먼저 생각해 볼 수 있는 것은 먼저 부분합을 구한 후 사용하는 것 이지만,

중간의 수열 내 값이 변할 수 있기 때문에, 적절한 접근은 아니다.

두번째는 이차원 배열을 이용하는 것이지만, N 이 최대 1,000,000 이므로 메모리가 초과할 것이다.

여기서 구간 트리(혹은 Segment tree) 라는 것을 사용 해 볼 수 있다.

구간 트리는 저장된 자료들을 적절히 전처리하여 이후 쿼리를 빠르게 대응 할 수 있도록 한다.

구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다.

루트는 항상 배열의 전체 구간을 포현하며,

왼쪽과 오른쪽 자식은 부모 노드가 표현하는 구간의 왼쪽 절반, 오른쪽 절반을 표현한다.

길이가 1인 구간은 트리의 leaf 가 된다.

구간 트리는 보통 배열로 구현하며,

왼쪽 자식 노드를 idx*2

오른쪽 자식 노드를 idx*2 + 1 로 표현할 수 있다.

적절한 메모리 공간은 쉽게 하면 전체 구간의 4배 정도이다.

구간 트리 구현을 위해서는 크게 3가지 기능을 하는 함수 정의가 필요하며,

모두 재귀적으로 동작한다.

init 의 구현은 간단한다.

query 의 구현은 그림으로 이해하는 편이 좋다.

update 의 구현 역시 그림으로 이해하는 편이 좋다.

[3. 코드]

test_kernelv2