[자료구조/문제] 구간합, BOJ 2042, Binary Indexed Tree

문제 : https://www.acmicpc.net/problem/2042

N개의 주어진 수가 빈번히 변경이 일어날 때, 중간에 어떤 구간에 대해 합을 구하는 문제이다.

구간에 대해 합, 최소, 최대를 해결하는 자료구조는

- Segment Tree

- Interval Tree

- Indexed Tree

가 있는데, 그 중 Binary Indexed Tree를 사용하여 문제를 풀도록 하겠다.

문제풀이

1. 트리구성하기

  1) 2의 n제곱으로 Tree를 구성해야 하므로, 실제 트리 개수를 구한다.

  2) 트리의 맨 아래 노드, 위쪽 노드를 채운다.

노드의 index가 i일때, 부모 노드의 번호는 i/2, 왼쪽 자식의 노드 번호는 i*2, 오른쪽 자식의 노드 번호는 i*2+1 이다.

이 성질을 이용하여 tree의 값을 채운다.

2. 값 갱신하기

3. 구간합 더하기

1) 왼쪽 노드를 L, 오른쪽 노드를 R이라고 했을 때, 각각 자신의 부모를 찾는다.

2) 이 때, L은 자기 자기 자신을 기준으로 왼쪽으로 선을 긋고, R은 자기 자신을 기준으로 오른쪽으로 선을 그었을 때

구역의 범위를 벗어나지 않아야 한다. 

3) L이 왼쪽 자식일 경우 부모 노드로 이동한다.

4) L이 오른쪽 자식일 경우 합산에 더하고 오른쪽으로 옮긴 다음 부모 노드로 이동한다.

5) R이 왼쪽 자식일 경우 합산에 더하고 왼쪽으로 옮긴 다음 부모 노드로 이동한다.

6) R이 오른쪽 자식일 경우 부모 노드로 이동한다.

7) L과 R이 교차하거나 만나면 탐색을 종료한다.

참고 사이트 : http://blog.naver.com/choyi0521/80204274208