세그먼트 트리 - (Segment Tree)

 

Segment Tree

 

 

 

(입력)

 

-> 배열 A[n], 두 정수 a, b ( 0<=a, b<n )

 

 

 

(출력)

 

-> Sum(a,b) = A[a] + A[a+1] + ... + A[b]

 

 

 

(갱신)

 

-> Update(i,x) : A[i] = x

 

 

 

 

 

(Brute-force method)

-> No preprocessing. - 전처리없이 하면

-> O(n) in the worst case - 시간복잡도가 O(n)일 것이다.

 

 

 

 

 

 

 

 

 

 

사진출처 : 백-준

 

 

 

배열의 부분합을 쳐 여어놓으라고

 

이거 나중에 문제푸는데 쓴데

 

배열에서 구간 합 근데 트리에서 이미 구한 값을 이용해서

구하면 쉬웅게

 

 

 

이렇게,

 

 

 

 

long long sum(vector<long long> &tree, int node, int start, int end, int left, int right)
{
	if(left>end || right < start)
    {
    return 0;
    }
    if (left <= start && end <= right)
    {
    return tree[node];
    }
    return sum(tree, node*2, start, (start+end)/2, left, right) + sum(tree, node*2+1, (start+end)/2+1, end, left, right);
}

 

근데 이거 만약에 배열안에 숫자가 바뀌면

 

좀 복잡해짐 근데 내 머리가 더 복잡함 지금