526互联

线段树

发布时间 2023-09-02 16:43:48作者: hnzzlxs01

建树：

int a[100005],d[100005];
void build(int s,int e,int p){// 建树
	// 对区间[s,t]建立线段树，当前根编号为p
	if(s==e){
		d[p]=a[s];
		return ;
	}
	int m=s+((e-s)>>1);
	build(s,m,p*2);
	build(m+1,e,p*2+1);// 分割出两个子区间
	d[p]=d[p*2]+d[(p*2)+1];
}// d[i]为编号i节点保存的值为d[i]

区间查询：

int find(int l,int r,int s,int e,int p){//区间查询（基础版）
	// [l, r] 为查询区间, [s, e] 为当前节点包含的区间, p 为当前节点的编号
	if(l<=s&&e<=r){
		return d[p];
	}// 当前区间为询问区间的子集时直接返回当前区间的和
	int mid=s+((e-s)>>1),sum=0;
	if(l<=mid)sum+=find(l,r,s,mid,p*2);
	// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
	if(r>mid)sum+=find(l,r,mid+1,e,p*2+1);
	// 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
	return sum;
}

int find_change(int l,int r,int s,int e,int p){//区间查询（修改版）
	// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
	if(l<=s&&e<=r){
		return d[p];
	}// 当前区间为询问区间的子集时直接返回当前区间的和
	int mid=s+((e-s)>>1);
	if(b[p]!=0){
		d[p*2]+=b[p]*(mid-s+1);
		d[p*2+1]+=b[p]*(e-mid);
		// 修改当前节点
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		// 将标记下传给子节点
		b[p]=0;
		// 清空当前节点的标记
	}
	int sum=0;
	if(l<=mid)sum+=find_change(l,r,s,mid,p*2);
	// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
	if(r>mid)sum+=find_change(l,r,mid+1,e,p*2+1);
	// 如果右儿子代表的区间[mid+1,r]与询问区间有交集，则递归查询右儿子
	return sum;
}

区间修改

void add(int l,int r,int c,int s,int e,int p){//区间修改(区间加上某个值)
	// [l, r] 为修改区间, c为被修改的元素的变化量, [s, t] 为当前节点包含的区间
    // p为当前节点的编号
    if(l<=s&&e<=r){
    	//d[p]+=(e-s+1)*c;
    	d[p]+=(e-s+1)*c;
		b[p]+=c;
    	return ;
	}// 当前区间为修改区间的子集是直接修改当前值，然后打标记，结束修改
	int mid=s+((e-s)>>1);
	if(b[p]!=0&&s!=e){
		// 若当前节点的标记为空，则更新该节点两个子节点的值和标记值
		d[p*2]+=b[p]*(mid-s+1);
		d[p*2+1]+=b[p]*(e-mid);
		// 修改当前子节点的值
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		// 将标记下传给子节点
		b[p]=0;
		// 清空当前节点的标记
	}
	if(l<=mid)add(l,r,c,s,mid,p*2);
	// 处理左子节点
	if(r>mid)add(l,r,c,mid+1,e,p*2+1);
	// 处理右子节点
	d[p]=d[p*2]+d[p*2+1];
	// 修改当前节点的值
}

模板题：P3372 【模板】线段树 1

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 $k$。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 $n, m$，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 $[x, y]$ 内每个数加上 $k$。
  2. 2 x y：输出区间 $[x, y]$ 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

11
8
20

提示

对于 $30%$ 的数据：$n \le 8$，$m \le 10$。
对于 $70%$ 的数据：$n \le {10}^3$，$m \le {10}^4$。
对于 $100%$ 的数据：$1 \le n, m \le {10}^5$。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$。

【样例解释】

解析及代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,op,x,y,k;
int a[1000005],d[1000005],b[1000005];
// a为原数组，d为线段树数组，b为标记数组
void build(int s,int e,int p){// 建树
	// 对区间[s,e]建立线段树，当前根编号为p
	if(s==e){
		d[p]=a[s];
		return ;
	}
	int mid=s+((e-s)>>1);
	build(s,mid,p*2);
	build(mid+1,e,p*2+1);// 分割出两个子区间
	d[p]=d[p*2]+d[(p*2)+1];
}// d[i]为编号i节点保存的值为d[i]
int find(int l,int r,int s,int e,int p){//区间查询（基础版）
	// [l, r] 为查询区间, [s, e] 为当前节点包含的区间, p 为当前节点的编号
	if(l<=s&&e<=r){
		return d[p];
	}// 当前区间为询问区间的子集时直接返回当前区间的和
	int mid=s+((e-s)>>1),sum=0;
	if(l<=mid)sum+=find(l,r,s,mid,p*2);
	// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
	if(r>mid)sum+=find(l,r,mid+1,e,p*2+1);
	// 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子
	return sum;
}
void add(int l,int r,int c,int s,int e,int p){//区间修改(区间加上某个值)
	// [l, r] 为修改区间, c为被修改的元素的变化量, [s, t] 为当前节点包含的区间
    // p为当前节点的编号
    if(l<=s&&e<=r){
    	//d[p]+=(e-s+1)*c;
    	d[p]+=(e-s+1)*c;
		b[p]+=c;
    	return ;
	}// 当前区间为修改区间的子集是直接修改当前值，然后打标记，结束修改
	int mid=s+((e-s)>>1);
	if(b[p]!=0&&s!=e){
		// 若当前节点的标记为空，则更新该节点两个子节点的值和标记值
		d[p*2]+=b[p]*(mid-s+1);
		d[p*2+1]+=b[p]*(e-mid);
		// 修改当前子节点的值
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		// 将标记下传给子节点
		b[p]=0;
		// 清空当前节点的标记
	}
	if(l<=mid)add(l,r,c,s,mid,p*2);
	// 处理左子节点
	if(r>mid)add(l,r,c,mid+1,e,p*2+1);
	// 处理右子节点
	d[p]=d[p*2]+d[p*2+1];
	// 修改当前节点的值
}
int find_change(int l,int r,int s,int e,int p){//区间查询（修改版）
	// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
	if(l<=s&&e<=r){
		return d[p];
	}// 当前区间为询问区间的子集时直接返回当前区间的和
	int mid=s+((e-s)>>1);
	if(b[p]!=0){
		d[p*2]+=b[p]*(mid-s+1);
		d[p*2+1]+=b[p]*(e-mid);
		// 修改当前节点
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		// 将标记下传给子节点
		b[p]=0;
		// 清空当前节点的标记
	}
	int sum=0;
	if(l<=mid)sum+=find_change(l,r,s,mid,p*2);
	// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
	if(r>mid)sum+=find_change(l,r,mid+1,e,p*2+1);
	// 如果右儿子代表的区间[mid+1,r]与询问区间有交集，则递归查询右儿子
	return sum;
}
signed main(){
	//cin>>n>>m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		//cin>>a[i];
		scanf("%lld",&a[i]);
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		//cin>>op;
		scanf("%lld",&op);
		if(op==1){
			//cin>>x>>y>>k;
			scanf("%lld%lld%lld",&x,&y,&k);
			add(x,y,k,1,n,1);
		}else if(op==2){
			//cin>>x>>y;
			scanf("%lld%lld",&x,&y);
			//cout<<find_change(x,y,1,n,1)<<endl;
			printf("%lld\n",find_change(x,y,1,n,1));
		}
	}
	return 0;
}