首页 > 其他 > 详细

线段树(Segment Tree)

时间:2020-01-18 23:57:34      阅读:159      评论:0      收藏:0      [点我收藏+]

建立线段树

void build_tree(int arr[],int tree[],int node,int start,int end){

	if(start==end){
		tree[node] = arr[start];//叶子节点
	}
	else{
		int mid = (start + end)/2;
		int left_node = 2*node + 1;
		int right_node = 2*node + 2;
		build_tree( arr, tree, left_node, start, mid);//递归建左子树
		build_tree( arr, tree, right_node, mid+1, end);//递归建右子树
		tree[node] = tree[left_node] + tree[right_node];//维护
	}
}
         

 

更新某元素

void update_tree(int arr[],int tree[],int node, int start, int end,int idx, int val){
	 
	 if(start == end){
	 	arr[idx] = val;
	 	tree[node] = val;
	 }
	 
	 else{
	 	int mid = (start + end)/2;
	 	int left_node = 2*node +1;
	 	int right_node = 2*node +2;
	 	if(idx >= start &&idx <= mid){
	 		update_tree( arr, tree, left_node, start, mid, idx, val);
	 	}
	 	else{
	 		update_tree( arr, tree, right_node, mid+1, end, idx, val);
	 	}
	 	tree[node] = tree[left_node]+tree[right_node];
	}
}

  

 

查询区间和

int query_tree(int arr[], int tree[], int node, int start, int end, int L, int R){
	if(R<start||L>end){
		return 0;
	}else if(start == end||start>=L&&end<=R){//这里如果没有后面的,则每次查询都会一直递归到叶子节点,降低效率
		return tree[node];
	}
	else{
	
	
		int mid = (start+end)/2;
		int left_node = 2*node + 1;
		int right_node = 2*node+2;
		int sum_left = query_tree( arr, tree, left_node, start, mid, L, R);
		int sum_right = query_tree( arr, tree, right_node, mid+1, end, L, R);
		return sum_left+sum_right;
	}

 

区间操作(加法)

void plus_tree(int arr[],int tree[],ll node,ll start,ll end,ll L,ll R,ll num){
	if(start == end){
		tree[node] += num;
	}
	else {
		int mid = (start+end)/2;
		int left_node = 2*node+1;
		int right_node = 2*node+2;
		if(L<=mid){
			plus_tree(arr, tree, left_node, start, mid, L, R, num);
		}
		if (R>=mid+1){
			plus_tree(arr, tree, right_node, mid+1, end, L, R, num);
		}
		
		tree[node] = tree[left_node]+tree[right_node];
	}
}

  

 

 

 

线段树(Segment Tree)

原文:https://www.cnblogs.com/ranbom/p/12209253.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!