[Algorithm] Segment Tree (세그먼트 트리)

💡Segmet Tree (세그먼트 트리) 란?

세그먼트 트리는 Binary Tree로 리프노드가 배열의 원소이고, 부모 노드는 각 배열 원소의 값의 합입니다. 따라서 배열의 원소값이 계속 변하고, 배열의 부분 합을 구할 때 부분 합을 트리에 계속 저장하여 O(logN)의 속도로 빠르게 부분 합을 구할 수 있습니다. 

 

세그먼트 트리의 구현을 배열을 통해 구현 할 수 있다. 인덱스 i를 기준으로 했을 경우, 각 노드의 위치는 아래와 같습니다.

- 부모노드 : i

- 왼쪽 자식 노드 : 2*i

- 오른쪽 자식 노드 : 2*i + 1

 

📌세그먼트 트리 구현 함수

void init(int tree[], int arr[], int left, int right, int idx)
{
	if(left == right)
    {
    	tree[idx] = arr[left];
        return;
     }
     int midx = left + (right - left) / 2;
     init(tree, arr, left, mid, 2*idx);   		//left child
     init(tree, arr, mid+1, right, 2*idx + 1);  	// right child
     tree[idx] = tree[2*idx] + tree[2*idx + 1];		//merget tree
 }

 

📌구간 합을 구하는 함수

int sum(int tree[], int from, int to, int left, int right, int idx)
{
	if (from>right || to < left){
    	return 0;
    }
    if(from <= left && right <= to){
    	return tree[idx];
    }
    
    int mid = left + (left - right)/2;
    
   return sum(tree, from, to, left, mid, 2*idx) + sum(tree, from, to, mid+1, right, 2*idx+1);
}

 

---

💻참고글

www.notion.so/Segment-Tree-1-Segment-Tree-26cb6df01c584c1bb6411f10a9cf9327

백준 : https://www.acmicpc.net/blog/view/9

세그먼트 트리 (Segment Tree)

💻관련문제

백준 - 구간합구하기 : www.acmicpc.net/problem/2042