学习笔记四

线段树

数据结构在noi比赛中的重要性不言而喻，我们已经学了两个十分简洁有神奇的数据结构，现在我来看一个又长又好用的线段树。
首先我们要知道线段树可以干啥，区间之间的操作，单点查询，区间查询，区间修改什么的，记住有了线段树以后就不要在用O（n）的暴力搜索了。
建树。。。。
线段树的本质是一个二叉树，我们用递归的方法来建树，用回溯的方法来确定定值，只要到叶子结点赋值并且返回。代码如下：

void build(int l,int r,int o){
	if(l==r) {
		tree[o]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*o);
	build(mid+1,r,2*o+1);
	tree[o]=tree[2*o]+tree[2*o+1];
}

单点查询。。。。
这个也很简单，如果该点在mid左就照左孩子，在右边就找右孩子，找到了就返回，这个比较无聊我们可以直接跳过它的代码。

单点修改。。。。
这个和单点查询差不多，不断的找左右孩子，就OK了，代码如下：

int dandian(int x,int k,int l,int r,int o){
	if(l==r&&r==x){
		tree[o]+=k;
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x) dandian(x,k,l,mid,2*o);
	if(mid<x) dandian(x,k,mid+1,r,2*o+1); 
	tree[o]=tree[2*o]+tree[2*o+1];
}

区间修改。。。。
这里面我们就要用到线段树的精华，懒标记。假设我们找到的区间完全包含于要修改的区间里，那么我们就修改这个区间的值，并且我们要记得给他打上懒标记，并且返回，这里就体现了线段树的精髓，标记而不下推，在查询是再去更改。假如不完全包含，那么我们就看看左边有交集就找左边，右边有交集就找右边，等到完全包含再去修改并且打上懒标记。下推懒标记的pushdown也在下面。代码如下：

int lazy[40000]={0};
void pushdown(int l,int r,int o){
	if(lazy[o]!=0){
		lazy[2*o]+=lazy[o];
		lazy[2*o+1]+=lazy[o];
		tree[2*o]+=l*lazy[o];
		tree[2*o+1]+=r*lazy[o];
		lazy[o]=0;
	}
}

void change(int l,int r,int c,int d,int u,int o){//给c到d上的每一个数字加u 
	if(l>=c&&r<=d){
		tree[o]+=u*(l-r+1);
		lazy[o]+=u;
		return;
	}
	int mid=(l+r)/2;
	pushdown(mid-l+1,r-mid,o);
	if(mid>=c) change(l,mid,c,d,u,2*o);
	if(mid<d) change(mid+1,r,c,d,u,2*o+1);
	tree[o]=tree[2*o]+tree[2*o+1]; 
}

区间查询。。。。
还是和刚才一样如果完全包含就加上。如果完全不包含就返回0（这是一个保障和优化），之后我们一定要pushdown，给之前没干的事情一个补偿，之后如果左边包含就找左边，右边包含就找右边。代码如下：

void search(int l,int r,int c,int d,int o){
	if(l>=c&&r<=d){
		return tree[o];
	}
	int mid=(r+l)/2;
	pushdown(mid-l+1,r-mid,o);
	int ans=0;
	if(mid>=c) ans+=search(l,mid,c,d,2*o);
	if(mid<d) ans+=search(mid+1,r,c,d,2*o+1);
	return ans;	
}