세그먼트 트리와 펜윅 트리 - 효율적인 범위 쿼리를 위한 자료구조

 

• 세그먼트 트리(Segment Tree)란 무엇인가?

 

세그먼트 트리(Segment Tree)는 배열과 같은 데이터를 효율적으로 처리하기 위해 설계된 자료구조입니다. 이 자료구조는 주로 배열의 구간 합, 최댓값, 최솟값 등을 효율적으로 계산하기 위한 방법으로 사용됩니다. 세그먼트 트리는 트리 구조를 사용하여 **구간 범위 쿼리(range query)**와 **구간 업데이트(range update)**를 빠르게 수행할 수 있게 해줍니다.

 

세그먼트 트리의 특징은 트리의 각 노드가 배열의 일정 범위에 대한 정보를 저장한다는 점입니다. 예를 들어, 구간 합을 구하는 경우, 트리의 각 노드는 배열의 부분 구간에 대한 합을 저장하며, 이를 통해 특정 구간의 합을 O(log N) 시간에 계산할 수 있습니다.

 

세그먼트 트리 구조:

• • 노드: 각 노드는 배열의 일부 구간을 나타냅니다.
• • 루트 노드: 전체 배열을 나타내는 노드입니다.
• • 리프 노드: 배열의 각 원소를 나타냅니다.

 

세그먼트 트리의 예시:

         [1, 2, 3, 4, 5, 6, 7, 8]
              /           \
         [1, 2, 3, 4]    [5, 6, 7, 8]
          /    \           /     \
      [1, 2] [3, 4]    [5, 6]  [7, 8]
      /   \   /   \    /   \   /   \
     [1] [2] [3] [4] [5] [6] [7] [8]

  

위의 세그먼트 트리는 배열 [1, 2, 3, 4, 5, 6, 7, 8]에 대한 세그먼트 트리입니다. 각 부모 노드는 자식 노드들의 정보를 합산하여 저장합니다.

 

• 세그먼트 트리의 주요 연산

1. 구간 합 구하기 (Range Query):

세그먼트 트리를 사용하면, 배열의 임의 구간에 대한 합을 빠르게 계산할 수 있습니다. 구간 합을 계산할 때는 트리에서 해당 구간에 대응하는 노드를 찾아서 값을 합산합니다. 이 연산은 O(log N) 시간이 걸립니다.

2. 구간 업데이트 (Range Update):

세그먼트 트리는 배열의 일부 구간을 변경할 수 있습니다. 트리에서 구간에 해당하는 값을 업데이트한 후, 부모 노드들도 값을 갱신해야 합니다. 이 연산 역시 O(log N) 시간이 걸립니다.

 

세그먼트 트리의 장점:

• • 구간 쿼리와 구간 업데이트가 모두 O(log N) 시간 복잡도를 가집니다.
• • 트리 구조이므로, 구간 합, 최댓값, 최솟값 등 다양한 구간 쿼리 문제에 유용합니다.

 

단점:

• • 메모리 사용량이 많습니다. 배열의 크기가 N이면, 세그먼트 트리는 대체로 **O(4N)**의 크기를 가집니다.

 

• 펜윅 트리(Fenwick Tree)란 무엇인가?

 

펜윅 트리(Fenwick Tree), 또는 **Binary Indexed Tree (BIT)**는 세그먼트 트리보다 더 간단하고 효율적인 구간 합 계산 자료구조입니다. 펜윅 트리는 배열에 대한 구간 합 쿼리와 구간 업데이트를 O(log N) 시간에 처리할 수 있습니다. 세그먼트 트리와 마찬가지로 범위 쿼리를 효율적으로 처리하지만, 구현이 더 간단하고 메모리 사용량도 적습니다.

 

펜윅 트리는 트리 구조를 사용하지 않고, 배열을 사용하여 구간 합을 빠르게 계산합니다. 배열의 각 원소는 자신과 관련된 구간 합을 저장하고 있으며, 이를 통해 구간 합 계산과 업데이트를 매우 빠르게 수행할 수 있습니다.

 

펜윅 트리의 구조:

• 펜윅 트리는 배열 기반으로 구현되며, 트리 구조처럼 부모 노드가 자식 노드를 직접 가리키는 방식이 아니라 배열의 각 원소가 특정 구간 합을 저장합니다.

 

펜윅 트리의 예시:

배열: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
펜윅 트리 구조:
Index:  1   2   3   4   5   6   7   8   9   10
       [1] [3] [3] [10] [15] [5] [21] [36] [45] [55]

 

펜윅 트리는 배열의 각 요소가 자신과 관련된 구간 합을 저장합니다. 예를 들어, 펜윅 트리[3]는 배열의 1번째부터 3번째까지의 합을 저장하고, 펜윅 트리[5]는 배열의 1번째부터 5번째까지의 합을 저장합니다.

 

• 펜윅 트리의 주요 연산

1. 구간 합 구하기 (Range Query):

펜윅 트리에서 구간 합을 구할 때는, 트리에서 해당 구간에 대응하는 값을 빠르게 계산합니다. 구간 합을 구하는 데 필요한 연산은 O(log N) 시간이 걸립니다.

2. 구간 업데이트 (Point Update):

펜윅 트리는 구간 업데이트는 지원하지 않지만, 포인트 업데이트를 지원합니다. 배열의 특정 원소를 업데이트하면, 펜윅 트리에서는 해당 값만 갱신되고, 관련된 부모 노드들도 갱신됩니다. 업데이트 연산은 O(log N) 시간이 걸립니다.

 

펜윅 트리의 장점:

• • 구현이 간단하고, 메모리 사용이 적습니다.
• • 구간 합과 업데이트 연산이 O(log N) 시간 복잡도로 효율적으로 처리됩니다.

 

단점:

• • 구간 업데이트에는 제약이 있으며, 포인트 업데이트만 가능합니다.
• • 세그먼트 트리보다는 기능이 제한적입니다.

 

• 세그먼트 트리 vs 펜윅 트리

특징	세그먼트 트리	펜윅 트리
구조	트리 기반	배열 기반
구간 쿼리 시간	O(log N)	O(log N)
구간 업데이트 시간	O(log N)	O(log N) (포인트 업데이트만 지원)
메모리 사용	O(4N)	O(N)
구현 난이도	상대적으로 복잡	간단
활용 가능성	다양한 구간 쿼리 (합, 최댓값, 최솟값 등)	구간 합 계산에 주로 사용

 

세그먼트 트리는 구간 합을 포함한 다양한 구간 쿼리를 지원하는 반면, 펜윅 트리는 구간 합 계산에 특화된 자료구조입니다. 펜윅 트리는 메모리 효율이 뛰어나고 구현이 간단하지만, 구간 업데이트와 같은 특정 연산에 제약이 있습니다. 반면, 세그먼트 트리는 더 많은 기능을 제공하지만, 상대적으로 메모리 사용량이 많고 구현이 복잡합니다.

 

• 결론

 

세그먼트 트리와 펜윅 트리는 범위 쿼리 문제를 효율적으로 해결하기 위한 중요한 자료구조입니다. 세그먼트 트리는 다양한 구간 연산을 처리할 수 있으며, 펜윅 트리는 메모리 효율성이 뛰어나고 간단한 구현으로 구간 합 계산에 유용합니다. 문제에 따라 적절한 자료구조를 선택하여 효율적인 처리를 할 수 있습니다.

 

참고 자료

• • 세그먼트 트리: https://en.wikipedia.org/wiki/Segment_tree
• • 펜윅 트리: https://en.wikipedia.org/wiki/Fenwick_tree