구간 트리 솔루션

[1. 개요]

구간 트리란?

• 보통 일차원 배열을 대상으로 특정 구간에 대한 쿼리를 O(logn) 에 할 수 있다.
• 구간 트리를 대상으로 하는 연산은 크게 3가지로 아래와 같다.
  1. init()
  2. query()
  3. update()

구간 트리 존재 의의

• 특정 구간의 합은 부분합으로 더 빠르게 O(1) 만에 구할 수 있지만,
• 어떤 원소의 값이 바뀌면 O(n) 의 시간을 들여 부분 합을 다시 만들어야 한다.
• 구간 트리는 O(logn) 으로 update 하고, 구간의 합을 O(logn) 으로 구할 수 있다.

구간 트리 구현을 아래와 같이 한가지 패턴으로 작성하도록 한다.

1. u        # 구간 트리의 노드 번호, (Root 의 노드 번호는 1 이다.)
2. left     # u 의 포함되는 구간의 가장 왼쪽
3. right   # u 의 포함되는 구간의 가장 오른쪽
4. from   # query 혹은 update 할 구간의 가장 왼쪽
5. to       # query 혹은 update 할 구간의 가장 오른쪽
6. index # update 할 element 의 index  

init() 구현 패턴 (재귀적으로 구현)

• 함수 프로토타입
  => func(u, left, right)
•  기저 사례
  left == right 인 경우,
  단말노드가 되는 경우
  => segTree[u] 에 구간트리가 표현해야 하는 값을 저장.
• mid = (left + right) / 2
• func(2*u, left, mid)                # [left, mid]
• func(2*u+1, mid+1, right)      # [mid+1, right]
• segTree[u] = segTree[2*u] <OP> segTree[2*u+1]

query() 구현 패턴 (재귀적으로 구현)

• 함수 프로토타입
  => func(u, left, right, from, to)
• 기저 사례
  1. 쿼리 할 구간 [from, to] 가 노드가 표현하는 구간 [left, right] 에 속하지 않는 경우
  => return 시 주의
  ==> 전체 결과에 영향을 주지 않는 값이 반환되어야 한다.
  ==> 구간의 곱을 구해야하는데 여기서 0을 반환하면 전체가 0이 되버린다면...
  
  2. 노드가 표현하는 구간 [left, right] 가 쿼리한 구간 [from, to] 에 완전히 속하는 경우
  => return segTree[u];
• mid = (left + right) / 2
• func(2*u, left, mid, from, to)                # [left, mid]
• func(2*u+1, mid+1, right, from, to)      # [mid+1, right]
• segTree[u] = segTree[2*u] <OP> segTree[2*u+1]
• return segTree[2*u] <OP> segTree[2*u+1]
  • node 에 저장 된 값을 바꿀 필요는 없다.

기저 사례 1

기저 사례 2

 

update() 구현 패턴 (재귀적으로 구현)

• 함수 프로토타입
  => func(u, left, right, index)
• 기저 사례
  1. index 가 구간 [left, right] 에 속하지 않는 경우
  => return segTree[u]
  ==> 노드 u 에 속한 구간의 값이 변경되지 않음, 이것을 그대로 반환.
  
  2. left == right, 단말 노드까지 내려온 경우
  => 여기선 index == left == right 이다.
  => segTree[u] = array[index] # 혹은 문제 조건에 맞게 업데이트 
  => return
• mid = (left + right) / 2
• func(2*u, left, mid, index)                # [left, mid]
• func(2*u+1, mid+1, right, index)      # [mid+1, right]
• segTree[u] = segTree[2*u] <OP> segTree[2*u+1]

update 기저 사례

 

구간트리 구현을 위해서는 보통 배열의 전체 구간의 4배에 해당하는 메모리가 필요하다.

따라서 아래와 같은 상황에서 구간 트리 사용을 고려해 볼 수 있다.

• 문제 조건에서 배열의 길이의 4배에 해당하는 메모리 확보가 가능하다면,
• 배열 내 데이터 변경이 빈번하다면,
• 특정 구간에 대해서 아래와 같은 쿼리를 요구한다면, (혹은 이러한 쿼리가 답을 구하는데 필요하다면)
  1. 최대 값
  2. 최소 값
  3. 구간의 합
  4. 구간의 곱
  5. 구간 내 데이터의 개수
  ...

구간트리 문제는 보통 단일 원소에 대한 update 가 주어지지만,

경우에 따라서는 전체 구간에 대한 update 가 필요 할 수 있다. 

• update 함수의 프로토타입이 바뀐다.
  => func(u, left, right, from, to)
• 구간에 대응되는 노드 u 까지만 내려가서 값을 업데이트 하고
• 변경된 구간에 속한 모든 leaf 들을 한꺼번에 취합하는 쪽으로 구현하는 경우가 있다.

Lazy propagation

• 구간을 포함하는 노드에 업데이트 값을 두고,
• 이 후, leaft 까지 내려가서 단계적으로 업데이트 하는 경우, 시간 초과 발생 가능성이 높다.
• Lazy propgation 을 이용하면, 해당 구간을 표현하는 노드에 접근했을 때, 구간 전체를 업데이트 하여
• 시간 초과 발생을 막을 수 있다.
• 관련 링크 및 예제
  • https://testkernelv2.tistory.com/565
  • https://testkernelv2.tistory.com/566

---

[2. 예제]

• https://testkernelv2.tistory.com/481
• https://testkernelv2.tistory.com/562
• https://testkernelv2.tistory.com/563
• https://testkernelv2.tistory.com/408
• https://testkernelv2.tistory.com/566
• f