구간 트리. [16975]

[1. 문제 설명]

길이가 N 인 수열이 있을 때, 아래 쿼리를 수행하는 프로그램을 작성

[2. 풀이 접근]

update 횟수가 최대 N 번이고

그 때마다 각 구간의 길이는 최대 N 일 수 있으므로,

단순하게 푼다면 N³

구간트리에서 단일 index 만 업데이트 한다면 N²logN 이 걸린다.

이 문제를 푸는 방법에는

Lazy Propagation, 팬윅트리(구간 트리의 다른 버전) 등이 있다고 하는데

위 방법을 사용하지 않고 풀 수 있다.

최초 구간트리 초기화 시,

구간 트리의 단말노드에만 값을 부여하고,

단말이 아닌 노드는 0을 초기화 한다.

# 아래 그림에서 구간의 길이가 1인 곳에만 배열에 설정 된 값을 부여하는 것이다.

일반적인 구간 트리의 연산에는

크게 update 와 query 가 있으며,

update 는 단일 index 에 대해서만 업데이트 하며,

query 는 구간에 대한 쿼리를 말하는데,

여기서는 반대로 생각해야 한다.

update 를 구간에 대해서 하고

query 를 단일 index 에 대해서만 해야 한다.

각 단말 노드가 index 와 같은 값으로 설정되어있다 생각하고,

구간 1~3 의 모든 원소에 4 를 더하는 연산을 진행하면 아래와 같은 형태가 된다.

이번에는 구간 3~4 의 모든 원소에 2를 더하는 연산을 진행하면 아래와 같이 된다.

구간을 완전히 포함했을 때, 해당 구간에 누적 된 값을 갱신하는 것이다.

이제 index 2 가 가리키는 값을 확인하면 아래와 같이 탐색을 해야 한다.

루트에서 2를 만날 때 까지 마주친 노드에 설정 된 값은

각각 4와 2 이다.

이 두 값을 더해주면 update 가 진행 된 후 A₂ 에 설정 된 값을 알게 된다.

[3. 코드]

test_kernelv2