Segment Tree

Segment Tree 사용 조건

1. 연산이 결합 법칙을 만족

2. 연산에 항등원이 존재

 

- 리프노드에 원본 데이터를 입력

vector<ll> tree;

int main() {

	int n;
	cin >> n;

	int height = 0;
	while((int)pow(2, height) < n){
		height++;
	}

	int treeSize = (int)pow(2, height+1);
	tree.resize(treeSize + 1, x); //항등원으로 초기화
	int leftNodeIndex = treeSize/2;

	for(int i = leftNodeIndex; i < leftNodeIndex+n; i++){
		cin >> tree[i];
	}

	build(treeSize-1);
	//update(node + leftNodeIndex - 1, val);
	//query(start + leftNodeIndex - 1, end + leftNodeIndex - 1)

	return 0;
}

 

- build, query, update 함수를 연산에 따라 작성

//구간합
void build(int i){
	while(i>1){
		tree[i/2] += tree[i];
		i--;
	}
}

ll query(int start, int end){
	ll ans = 0;

	while(start <= end){
		if(start%2 == 1) {
			ans += tree[start];
			start++;
		}
		if(end%2 == 0){
			ans += tree[end];
			end--;
		}
		start/=2;
		end/=2;
	}
	return ans;
}

void update(int node, ll val){
	ll diff = val - tree[node];
	while(node > 0){
		tree[node] += diff;
		node /= 2;
	}
}

//최솟값
void build(int i){
	while(i>0){
		tree[i] = min(tree[i*2], tree[i*2+1]);
		i--;
	}
}

ll query(int start, int end){
	ll ans = MAXSIZE;

	while(start <= end){
		if(start%2 == 1) {
			ans = min(tree[start], ans);
			start++;
		}
		if(end%2 == 0){
			ans = min(tree[end], ans);
			end--;
		}
		start/=2;
		end/=2;
	}
	return ans;
}

void update(int node, ll val){
    tree[node] = val;
    node /= 2;
    while(node > 0){
        tree[node] = min(tree[node*2], tree[node*2 + 1]);
        node /= 2;
    }
}