세그먼트 트리 (Segment tree)

세그먼트 트리 (Segment tree)

---

  정의 

  세그먼트 트리 (Segment tree) 란, 1차원 배열의 값들을 포화 이진 트리를 활용하여 Bottom-up 을 통해 효율적으로 저장 및 탐색하는 자료구조 이다. 이 트리의 리프 노드들은 순서대로 배열의 원소들에 해당이 되며, 내부 노드들은 아래 두 자식 노드에 해당이 되는 배열의 원소들을 합한 범위의 원소들에 대한 연산 값을 나타낸다. 

---

  트리 구현 

 

 

  트리의 각 노드들은 배열에서 트리에 해당되는 구간의 원소들의 합의 값을 가지고 있다.

---

  설명 

  세그먼트 트리는 Bottom-up 방식으로 구현이 된다. 이를 위해선, 리프 노드들을 배열의 원소들로 우선적으로 초기화를 시켜준다. 리프노드의 시작 노드는 배열의 개수보다 큰 2의 제곱수 들 중 최소값이다. 즉 위 트리에선 리프노드의 시작 노드는 16번째 노드가 된다. 16번째 노드부터 총 배열의 원소의 개수만큼 증가되는 노드까지 배열의 각 원소에 해당되는 리프노드가 된다. (16번째 ~ 25번째) 그리고 배열의 원소들의 개수가 2의 제곱수가 아닌 이상 트리의 우측에는 위 트리처럼 사용하지 않는 노드가 된다.

 

  리프 노드들부터 트리의 깊이를 줄여가면서 초기화를 한다. 위 트리의 경우 리프노드들이 트리의 4의 깊이에 해당되는 노드들에 있으므로, 이후 3, 2, 1, 그리고 루트노드인 0깊이에 해당되는 노드를 초기화를 한다. 내부 노드들을 초기화를 할 땐 아래 두 자식노드들의 값만 참고하면 되므로, 이러한 방식으로 초기화를 진행할 수 있다.

 

[초기화 코드] (구간 합 세그먼트 트리)

void init() {
	for (int i = s; i <= s + n - 1; i++)
		tree[i] = list[i - s + 1];

	int curNode = s >> 1;

	while (curNode) {
		for (int i = curNode; i < curNode << 1; i++)
			tree[i] = tree[i << 1] + tree[(i << 1) + 1];

		curNode >>= 1;
	}
}

---

  세그먼트 트리에서 배열의 어떤 원소의 값을 변경해야 할 때가 있을 것이다. 변경을 하면 그 원소가 포함되어있는 트리의 노드들의 값을 모두 바꿔야 한다. 트리에서 배열의 원소에 해당되는 리프노드가 변경되었을 때 값의 변동이 있을 노드들은 이 리프노드의 조상노드들만 해당이 된다. 따라서 변경하고자 하는 원소가 있는 트리의 라프노드부터 시작해서  계속해서 부모노드를 업데이트 하여 루트노드까지 값을 변경해 나가면 된다.

 

[업데이트 코드] (구간 합 세그먼트 트리)

void update(int curNode, const ll change) {
	while (curNode) {
		if (s <= curNode) tree[curNode] = change;
		else tree[curNode] = tree[curNode << 1] + tree[(curNode << 1) | 1];

		curNode >>= 1;
	}
}

 

  업데이트를 시작하고자 하는 노드와 바꾸려는 값을 파라미터로 넣으면 된다. 이 때, 원하는 배열의 원소가 담긴 부분은 트리에서 (리프노드의 시작 노드 + 배열의 index - 1) 번째 노드에 있다.

---

[쿼리 코드] (구간 합 세그먼트 트리)

ll query(int l, int r) {
	ll ret = 0;

	for (l += s - 1, r += s - 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) ret += tree[l++];
		if (!(r & 1))ret += tree[r--];
	}

	if (l == r) ret += tree[l];

	return ret;
}

 

  비트마스킹을 활용하여 쿼리 코드를 구현하였다. 이 코드는 배열에서 array[l] ~ array[r] 원소들의 합을 구한다. 마치 투 포인터 알고리즘처럼 l 과 r 을 서로 우측, 좌측으로 이동을 시키면서 부모노드에 접근을 할 수 있을땐 최대한 부모 노드에 접근을 하여 구간의 합을 구하게 된다. 만약 배열에서 2번째 ~ 9번째 원소들의 합을 구하고자 한다면 아래 그림처럼 트리에서 빨간 테두리가 쳐저있는 노드의 값들이 연산에 사용이 된다.