线段树

线段树真是太强啦!

用途

线段树不同与树状数组,他支持单点查询,单点修改,区间修改,区间查询,需要 \(4\) 个函数进行,分别为 \(build,updata,query,lazy\) 组成,即搭建,更新,查询,懒惰数组。

build 建树

定义一个数组,我们称为 \(tree\) 对于 \(tree_i\) 我们同样保留 \(4\) 个元素,\(l,r,num,lazy\) 分别记录左端点,右端点,端点和,和懒惰值。然后开始搭建树,我们搭建一颗完全二叉树第一层的元素记录 \(1\) 到 \(n\) 的元素和,第二层左儿子记录 \(1\) 到 \(n/2\) ,右儿子记录 \(n/2+1\) 到 \(n\) , 以此类推。父节点的值为子节点的值之和。
性质:对于任意一个父节点,令他的编号为 \(x\) ,则他的左儿子编号为 \(x \times 2\) ,右儿子为 \(x \times 2 +1\)。
Code:

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

updata 更新

先找到父亲所在的 \(tree\) 数组,打上懒惰数组(等下会讲),然后返回,否则,就继续找,一直到 \(l,r\) 的值都算出来。如果找的途中懒惰数组需要用到,就通过 \(lazy\) 操作让懒惰数组向儿子赋值。
Code:

	void updata(int l,int r,int k,int number){
	int left=tree[number].l,right=tree[number].r;
	if(left>r||right<l) return;
	if(l<=left&&right<=r){
		tree[number].num+=k*(right-left+1);
		tree[number].lazy+=k;
		return;
	}
	if(tree[number].lazy>0) lazy(number);
	updata(l,r,k,number*2);
	updata(l,r,k,number*2+1);
	tree[number].num=tree[number*2].num+tree[number*2+1].num;
	return;
}

lazy 懒惰数组

为什么线段树能支持区间修改?原因就是懒惰数组,对于每一次修改,如果我们只需要要求一个大区间的值,那么我们只需要修改大区间的值,根本不需要修改小区间的值。如果我们后面需要修改小区间的,我们在修改小区间即可。这样,就节省了时间。
Code:

        void lazy(int number){ //number 为节点编号
	tree[number*2].num+=(tree[number*2].r-tree[number*2].l+1)*tree[number].lazy;
	tree[number*2+1].num+=(tree[number*2+1].r-tree[number*2+1].l+1)*tree[number].lazy;
	tree[number*2].lazy+=tree[number].lazy;
	tree[number*2+1].lazy+=tree[number].lazy;
	tree[number].lazy=0;
	return;
}

query 查询

这个我就不多赘述,直行看代码即可理解。
Code:

    long long query(int l,int r,int number){
	int left=tree[number].l,right=tree[number].r;
	if(left>r||right<l) return 0;
	if(l<=left&&right<=r){
		return tree[number].num;
	}
	if(tree[number].lazy!=0) lazy(number);
	return query(l,r,number*2)+query(l,r,number*2+1);
}
}

Code

一个总代码,为洛谷 P3372 Ac代码

   #include<iostream>
using namespace std;
long long n,m,a[100005],x,y,z,k;
struct node{
	int l,r;
	long long num,lazy;
}tree[4*100005];
void build(int l,int r,int p){
	tree[p].l=l;
	tree[p].r=r;
	if(l==r){
		tree[p].num=a[l];
		return;
	}
	build(l,(l+r)/2,p*2);
	build((l+r)/2+1,r,p*2+1);
	tree[p].num=tree[p*2].num+tree[p*2+1].num;
	return; 
}
void updata(int number){
	tree[number*2].num+=(tree[number*2].r-tree[number*2].l+1)*tree[number].lazy;
	tree[number*2+1].num+=(tree[number*2+1].r-tree[number*2+1].l+1)*tree[number].lazy;
	tree[number*2].lazy+=tree[number].lazy;
	tree[number*2+1].lazy+=tree[number].lazy;
	tree[number].lazy=0;
	return;
}
void add(int l,int r,int k,int number){
	int left=tree[number].l,right=tree[number].r;
	if(left>r||right<l) return;
	if(l<=left&&right<=r){
		tree[number].num+=k*(right-left+1);
		tree[number].lazy+=k;
		return;
	}
	if(tree[number].lazy>0) updata(number);
	add(l,r,k,number*2);
	add(l,r,k,number*2+1);
	tree[number].num=tree[number*2].num+tree[number*2+1].num;
	return;
}
long long find(int l,int r,int number){
	int left=tree[number].l,right=tree[number].r;
	if(left>r||right<l) return 0;
	if(l<=left&&right<=r){
		return tree[number].num;
	}
	if(tree[number].lazy!=0) updata(number);
	return find(l,r,number*2)+find(l,r,number*2+1);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	build(1,n,1);
	while(m--){
		cin>>z;
		if(z==1) {
			cin>>x>>y>>k;
			add(x,y,k,1); 
		}else {
			cin>>x>>y;
			long long sum=find(x,y,1);
			cout<<sum<<endl;
		}
	}
	return 0;
}