线段树学习笔记

题面传送门
线段树每个根节点管理下面的两个叶子节点，线段树的每一个节点都分管区间，其中若根节点分管区间是\(x\)，\(y\)，那么左儿子区间为\(x\)，\((x+y)>>1\),右儿子分管区间是\(((x+y)>>1)+1\),\(y\).
我们定义\(f\)数组，以\(f_x\)表示\(x\)这个节点所管理的区间统一加了多少，定义\(sum_x\)表示\(x\)这个节点所管理的区间的和为多少。
线段树主要有三个环节:建树，修改，查询
建树:这很好建，一个递归，每一层的值为返回的两个儿子的值的和，叶子结点返回本来的单个单元的值，复杂度\(o(nlog^2n)\)。不要被这么高的复杂度吓到，毕竟总共就建一次树。
查询:线段树把一个区间分成好几个长度为二进制的区间之和，而二进制查找需要一个递归。
对于我们要把\(x\)到\(y\)的区间加上\(z\)，在进行到一个节点时，进行三种判断:若是查找区间包含这个节点所管理的区间，那么\(f_{now}\)加上\(z\)，\(return\)。若是\(x\)落在左儿子内，递归下去。若是\(y\)落在右儿子内，也递归下去。同时为了好理解，我们做一个下推动作，把\(f_x\)推到两个儿子的\(f\)数组中，把两个儿子的\(sum\)加上推下来的值。并把\(f_x=0\).这样已经做过的\(sum\)的值就表示这个节点所管辖的区间的和值。
查询:在查询\(x\)到\(y\)时我们也和修改一样。进行三种判断:若是查找区间包含这个节点所管理的区间，返回一个\(sum\)，\(return\)。若是\(x\)落在左儿子内，递归下去。若是\(y\)落在右儿子内，也递归下去。也同时下推，这样能保证值一定是正确的。
个人理解:其实线段树的优点就在于是拆解而不是像树状数组一样作差。不过缺点就是常数太大。但有\(zkw\)非递归式线段树常数较小。线段树当优化后可以是一种很好的数据结构，他的适用范围很广。
代码实现:

#include
#define re register
long long n,m,a[200039],x,y,z,f[800039];
long long s[800039];
inline void read(long long &x) {
	x=0;register char s=getchar();register int fs=1;
	while(s<'0'||s>'9'){if(s=='-')fs=-1;s=getchar();}
	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar();
	x*=fs;
}
inline void print(re long long x){
	if(x<0){putchar('-');print(-x);return;}
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
inline long long jianshu(re int now,re int l,re int r){
	if(l>=r) return s[now]=a[l];
	re int m=(l+r)>>1;
	return s[now]=jianshu(now<<1,l,m)+jianshu(now<<1|1,m+1,r);
}
inline void push(re int l,re int r,re int now){
	re int m=(l+r)>>1;
	f[now<<1]+=f[now];
	s[now<<1]+=f[now]*(m-l+1);
	f[now<<1|1]+=f[now];
	s[now<<1|1]+=f[now]*(r-m);
	f[now]=0;
}
inline void get(int l, int r,int now){
	if(x<=l&&y>=r){
		f[now]+=z;
		s[now]+=z*(r-l+1);
		return;
	}
	register int m=(l+r)>>1;
	push(l,r,now);
	if(x<=m) get(l,m,now<<1);
	if(y>m) get(m+1,r,now<<1|1);
	s[now]=s[now<<1]+s[now<<1|1];
	return;
}
inline long long  find(int l,int r,int now){
	if(x<=l&&y>=r)return s[now];
	re long long m=(l+r)>>1,fs=0;
	push(l,r,now);
	if(x<=m) fs+=find(l,m,now<<1);
	if(y>m) fs+=find(m+1,r,now<<1|1);
	return fs;
}
int main(){
	freopen("1.in","r",stdin);
	register int i;
	read(n);read(m);
	for(i=1;i<=n;i++) read(a[i]);
	jianshu(1,1,n);
	for(i=1;i<=m;i++){
		read(x);
		if(x==1){
			read(x);read(y);read(z);
			get(1,n,1);
		}
		else{
			read(x);read(y);
			print(find(1,n,1));
			putchar('\n');
		}
	}
	return 0;
}

同时我们也可以看看一个应用
题面传送门
这道题是贪心和线段树的结合，贪心思想有点像凌乱的yyy/线段覆盖。把奶牛们按右端点排序，并用遍历所有地点可上车的奶牛，若可上车挑选下车最晚的位置上车，这样能做到最优，并记录总牛数。而挑选下车最晚的位置上车可以用线段树维护。
代码实现:

#include
#include
using namespace std;
int n,m,k,sum[1039],ans,tot,f[1039],x,y,fs[1039];
struct yyy{
	int x,y,z;
}a[50039];
char s;
inline void read(int &x){
	x=0;s=getchar();
	while(s<'0'||s>'9') s=getchar();
	while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar();
}
inline bool cmp(yyy a,yyy b){
	return a.y>1;
	if(x<=m) get(l,m,now<<1);
	if(x>m) get(m+1,r,now<<1|1);
	if(sum[now<<1]>sum[now<<1|1])sum[now]=sum[now<<1],f[now]=f[now<<1];
	else sum[now]=sum[now<<1|1],f[now]=f[now<<1|1];
}
int main(){
	register int i,j;
	read(n);read(m);read(k);
	for(i=1;i<=n;i++) read(a[i].x),read(a[i].y),read(a[i].z);
	sort(a+1,a+n+1,cmp);
	for(i=1;i<=n;i++){
		for(j=0;j<=1038;j++) f[j]=0,sum[j]=-1;
		for(j=1;j<=k;j++)
		if(fs[j]<=a[i].x) x=j,y=fs[j],get(1,k,1);
		tot=sum[1];
		while(a[i].z&&a[i].x>=tot&&tot!=-1){
			fs[f[1]]=a[i].y;
			ans++;
			a[i].z--;
			x=f[1];y=-1;
			get(1,k,1);
			tot=sum[1];
		}
	}
	printf("%d",ans);
	return 0;
}