一颗普通的支持查询区间和,区间加的线段树的常数到底是多少?所谓的“大常数”到底是多大? 代码如下:
#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;
}
那如果是动态开点的线段树呢?支持区间最值或区间乘法的线段树呢?如果只支持单点加和单点查询的呢?有什么具体的计算方法吗?