线段树 | Wiliyaya's blog

线段树维护的信息类型

父范围上的某个信息可以用O(1)的时间从子范围的信息加工得到。
满足的信息，比如:累加和，最大值，最小值，不满足的信息，比如某范围上出现次数最多的数。

线段树的经典功能

1.范围查询
2.范围修改，包括范围内每个数增加，重置等等操作
单次调用的时间复杂度为O(log n)

线段树的范围修改功能，想要做到单次调用的时间复杂度为O(log n),有如下要求：

一段范围上统一进行进行了某种修改，可以用O(1)的时间，就把这段范围维护的信息加工出来

sum数组要准备的空间：相应高度的满二叉树
空间最省时，n为2的几次方，所以最省时也要log n + 1层；
对于一个普遍的n，(可以以10为例）树的高度最多会达到h＝logn ＋2 层，而高度为h＝log n +2的满二叉树有2^h-1个节点，即4*n-1个节点，因此sum准备4n个空间

//范围l~r,信息存在独立数组的i位置
//返回递归展开过程中出现的最大编号
int maxi(int l,int r,int i){
	if(l==r){
		return i;
	}else {
		//(l+r)>>1即(l+r)/2
		int mid=(l+r)>>1;
		//i<<1 = i*2; i<<1|1即1＊2＋1
		return max(maxi(l,mid,i<<1),maxi(mid+1,r,i<<1|1));
	}
}

void howManySpace(){
	 int n = 10000;
    int a = 0;
    int b = 0;
    double t = 0;
    for (int i = 1; i <= n; i++) {
        int space = maxi(1, i, 1);
        double times = (double) space / (double) i;
        cout << "范围[1~" << i << "]，" << "需要空间" << space << "，倍数=" << times << endl;
        if (times > t) {
            a = i;
            b = space;
            t = times;
        }
    }
    cout << "其中的最大倍数，范围[1~" << a << "]，" << "需要空间" << b << "，倍数=" << t << endl;
}

线段树用到辅助空间

int MAXN=100001;
long* arr=new long[MAXN];
long* sum=new long[MAXN<<2];//即＊4
long* add=new long[MAXN<<2];//延迟更新的标记，就是书上的lazy数组

线段树build代码

void build(int l,int r,int i){
	//递归的终止条件
	if(l==r){
		sum[i]=arr[l];
	}else {
		int mid=(l+r)>>l;
		build(l,mid,i<<1);
		build(mid+1,r,i<<1|1);
		up(i);
	}
	add[i]=0;
}

最开始调用的一定是build(1,n,1)(下标从1开始)

累加和信息的汇总

void up(int i){
	//父范围的累加和＝左范围的累加和＋右范围的累加和
	sum[i]=sum[i<<1]+sum[i<<1|1];
}

lazy信息的下发

void down(int i,int ln,int rn){
//ln代表左子树结点个数
	if(add[i]!=0){
		//发左
		lazy(i<<1,add[i],ln);
		//发右
		lazy(i<<1｜1，add[i],rn);
		//父范围lazy信息清空
		add[i]=0;
	}
}

lazy方法

void lazy(int i,long v,int n){
//i:位置；v：每个数增加多少；n:一共有几个数
	sum[i]+=v*n;
	add[i]+=v;
}

查询

注意查询的时候，也要结合懒更新机制，增加down过程

long query(int jobl,int jobr,int l,int r,int i){
	//任务的范围，数据的范围，对应的sum数组位置
	//其中jobl和jobr一直不变，l,r,i随递归在变
	if(jobl<=l && jobr>=r){
		return sum[i];
	}
	int mid=(l+r)>>1；
	down(i,mid-l+1,r-mid);//下发懒信息
	long ans=0;
	if(jobl<=mid){
		ans+=query(jobl,jobr,l,mid,i<<1);//加上左子树的sum值
	}
	if(jobr>mid){
		ans+=query(jobl,jobr,mid+1,r,i<<1|1);
	}
	
	return ans;
}
//因为查询操作没有修改数据信息，不需要汇总，所以不用up操作

范围修改

//jobl～jobr范围的每个数字加jobv
void add(int jobl,int jobr,long jobv,int l,int r,int i){
	if(jobl<=l && r<= jobr){ //全部在范围内
		lazy(i,jobv,r-l+1);
	}else {
		int mid=(l+r)>>1;
		down(i,mid-l+1,r-mid);
		if(jobl<=mid){
			add(jobl,jobr,jobv,l,mid,i<<1);
		}
		if(jobr>mid){
			add(jobl,jobr,jobv,mid+1,r,i<<1|1);
		}
		up(i);
	}
}

貌似洛谷有题

other

子范围的懒更新信息，发生的时间一定早于父范围上的懒更新信息
如果修改操作不是范围修改，而是单点修改，那么懒更新的机制就不用建立，也不需要lazy信息的下发，每次修改都是一走到底