线段树的常数到底有多大?
  • 板块灌水区
  • 楼主TKXZ133
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/11/10 19:46
  • 上次更新2023/10/27 03:29:47
查看原帖
线段树的常数到底有多大?
767096
TKXZ133楼主2022/11/10 19:46

一颗普通的支持查询区间和,区间加的线段树的常数到底是多少?所谓的“大常数”到底是多大? 代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100500;

int n,m,ino,inx,iny,ink;

struct sn{
	int l,r;
	ll sum;
	ll t;
}a[N<<2];

void push_up(int p){
	a[p].sum=a[p<<1].sum+a[p<<1|1].sum;
	return;
}

void add_t(int p,ll k){
	a[p].sum+=k*(a[p].r-a[p].l+1);
	a[p].t+=k;
	return;
}

void push_down(int p){
	if(a[p].t){
		add_t(p<<1,a[p].t);
		add_t(p<<1|1,a[p].t);
		a[p].t=0;
	}
	return;
}

void add_l(int p,int x,int y,int k){
	if(x<=a[p].l&&a[p].r<=y){
		add_t(p,k);
		return;
	} 
	push_down(p);
	int mid=(a[p].l+a[p].r)>>1;
	if(x<=mid) add_l(p<<1,x,y,k);
	if(y>mid) add_l(p<<1|1,x,y,k);
	push_up(p);
	return;
}

void build(int p,int inl,int inr){
	a[p].l=inl;
	a[p].r=inr;
	if(inl==inr){
		scanf("%lld",&a[p].sum);
		a[p].t=0;
		return;
 	}
	int mid=(inl+inr)>>1;
	build(p<<1,inl,mid);
	build(p<<1|1,mid+1,inr);
	push_up(p);
	return ;
}

ll ask_sum(int p,int x,int y){
	if(x<=a[p].l&&a[p].r<=y)
		return a[p].sum;
	push_down(p);
	int mid=(a[p].l+a[p].r)>>1;
	ll res=0;
	if(x<=mid) res+=ask_sum(p<<1,x,y);
	if(y>mid) res+=ask_sum(p<<1|1,x,y);
	push_up(p);
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d",&ino);
		if(ino==1){
			scanf("%d%d%d",&inx,&iny,&ink);
			add_l(1,inx,iny,ink);
		}
		else{
			scanf("%d%d",&inx,&iny);
			printf("%lld\n",ask_sum(1,inx,iny));
		}	
	}
	return 0;
}

那如果是动态开点的线段树呢?支持区间最值或区间乘法的线段树呢?如果只支持单点加和单点查询的呢?有什么具体的计算方法吗?

2022/11/10 19:46
加载中...