关于线段树
  • 板块学术版
  • 楼主microchip
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/11/21 11:15
  • 上次更新2023/11/5 07:37:34
查看原帖
关于线段树
241838
microchip楼主2020/11/21 11:15

我对照老师的代码敲的线段树如下

#include<bits/stdc++.h>
using namespace std;

long long tree[400050],n[100050],tag[400050];

long long ls(long long k){return k<<1;}
long long rs(long long k){return k<<1|1;}

void push_up(long long p){
	tree[p]=tree[rs(p)]+tree[ls(p)];
}

void build(long long p,long long pl,long long pr){
	tag[p]=0;
	if(pl==pr){tree[p]=n[pl];return;}
	long long mid=(pl+pr)/2;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}

void add_tag(long long p,long long pl,long long pr,long long d){
	tag[p]+=d;
	tree[p]+=d*(pr-pl+1);
}

void push_down(long long p,long long pl,long long pr){
	if(tag[p]!=0){
		long long mid=(pl+pr)/2;
		add_tag(ls(p),pl,mid,tag[p]);
		add_tag(rs(p),mid+1,pr,tag[p]);
		tag[p]=0;
	}
}

void update(long long L,long long R,long long p,long long pl,long long pr,long long d){
	if(L<=pl&&pr<=R){
		add_tag(p,pl,pr,d);
		return;
	}
	push_down(p,pl,pr);
	long long mid=(pl+pr)/2;
	if(L<=mid)update(L,R,ls(p),pl,mid,d);
	if(R>mid)update(L,R,rs(p),mid+1,pr,d);
	push_up(p);
}

long long query(long long L,long long R,long long p,long long pl,long long pr){
	if(pl>=L&&R>=pr)return tree[p];
	push_down(p,pl,pr);
	long long res=0;
	long long mid=(pl+pr)/2;
	if(L<=mid)res+=query(L,R,ls(p),pl,mid);
	if(R>mid)res+=query(L,R,rs(p),mid+1,pr);
	return res;
}

int main()
{
	long long num,h;
	cin>>num>>h;for(long long i=1;i<=num;i++)cin>>n[i];
	build(1,1,num);
	for(long long i=0;i<h;i++){
		long long a,b,c,d;
		cin>>a;
		if(a==1){
			cin>>b>>c>>d;
			update(b,c,1,1,num,d);
		}else{
			cin>>b>>c;
			cout<<query(a,b,1,1,num)<<endl;
		}
	}
	return 0;
}

我不断对照代码,不断把每个子函数与老师对照,找不出本质上的不同,但我总过不了样例,心态崩了

2020/11/21 11:15
加载中...