线段树入门到自闭

算法介绍

线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。
可以进行一些区间的修改和查询。

算法详解

线段树通用的build方法

void build(int k,int l,int r)
{
if(l==r)
{
sum1[k]=tree[l];//求和或者最值
sum2[k]=tree[l]*tree[l];//平方和
return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
pushup(k);//代表更新sum，这里可以是sum[k]=sum[(ls(k)]+sum[rs(k)]。
}


因为要进行区间的查询和修改,线段树还需要两个函数，check和update。check函数和update都用到了分治的思想。
简单的应用是区间修改+单点查询，区间查询+单点修改。
区间修改单点查询的思路是将区间标记，然后查询时从上到下加起来，直到叶子节点。区间查询+单点修改的思路是修改时直到叶子节点。单点的操作递归不会出现左右都有的情况，其余与区间操作类似。
下面的代码都是都是对区间进行操作的。

int check(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return sum[k];
int mid=(l+r)>>1;
int ans=0;
if(x<=mid)ans+=check(ls(k),l,mid,x,y);
if(y>mid)ans+=check(rs(k),mid+1,r,x,y);
return ans;
}


void ADD(int k,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y)
{
sum[k]+=v*(r-l+1);
return ;
}
int mid=(l+r)>>1;
if(x<=mid)ADD(ls(k),l,mid,x,y,v);
if(y>mid)ADD(rs(k),mid+1,r,x,y,v);
pushup(k);
}


算法进阶

线段树可以进行复杂的区间修改和区间查询操作，主要要用到pushdown函数和懒标记。
懒标记是修改的因子，在对某个节点进行操作时，如果不需要对其儿子节点进行操作，就尽在这个节点进行懒标记，如果后边会对儿子节点进行修改查询操作，就要pushdown,向下传递懒标记。还有一些特殊的根号线段树和除法线段树。

例题

P1471 方差

题意

题目要求维护区间并求区间的方差，通过化简可以得知，求解方差只需要维护区间平方和与区间和即可。

代码


int const maxn=1000005;
double sum1[maxn*2],sum2[maxn*2],tree[maxn],lazy[maxn*2];
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
return x*f;
}
void pushup(int k)
{
sum1[k]=sum1[ls(k)]+sum1[rs(k)];
sum2[k]=sum2[ls(k)]+sum2[rs(k)];
}
void build(int k,int l,int r)
{
if(l==r)
{
sum1[k]=tree[l];
sum2[k]=tree[l]*tree[l];
return;
}
int mid=(l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
pushup(k);
}
void pushdown(int k,int l,int r)//pushdown的写法一般是线段树题目的核心
{
int mid=(l+r)>>1;
sum2[ls(k)]+=lazy[k]*lazy[k]*(mid-l+1)+2*lazy[k]*sum1[ls(k)];
sum2[rs(k)]+=lazy[k]*lazy[k]*(r-mid)+2*lazy[k]*sum1[rs(k)];
sum1[ls(k)]+=lazy[k]*(mid-l+1);
sum1[rs(k)]+=lazy[k]*(r-mid);

lazy[ls(k)]+=lazy[k];
lazy[rs(k)]+=lazy[k];
lazy[k]=0;
}
double check1(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return sum1[k];

if(lazy[k])pushdown(k,l,r);//关键代码

int mid=(l+r)>>1;
double ans=0;
if(x<=mid)ans+=check1(ls(k),l,mid,x,y);
if(y>mid)ans+=check1(rs(k),mid+1,r,x,y);
return ans;
}
double check2(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)return sum2[k];

if(lazy[k])pushdown(k,l,r);//关键代码

int mid=(l+r)>>1;
double ans=0;
if(x<=mid)ans+=check2(ls(k),l,mid,x,y);
if(y>mid)ans+=check2(rs(k),mid+1,r,x,y);
return ans;
}
void ADD(int k,int l,int r,int x,int y,double v)
{
if(l>=x&&r<=y)
{
sum2[k]+=v*v*(r-l+1)+2*v*sum1[k];
sum1[k]+=v*(r-l+1);
lazy[k]+=v;
return ;
}

if(lazy[k])pushdown(k,l,r);//关键代码

int mid=(l+r)>>1;
if(x<=mid)ADD(ls(k),l,mid,x,y,v);
if(y>mid)ADD(rs(k),mid+1,r,x,y,v);
pushup(k);
}
main(void)
{
int n=read();
int m=read();
int x,y,cmd;
double k;
for(int i=1;i<=n;i++)
{
scanf("%lf",&tree[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&cmd,&x,&y);
if(cmd==1)
{
scanf("%lf",&k);
ADD(1,1,n,x,y,k);
}
if(cmd==2)
{
printf("%.4lf\n",check1(1,1,n,x,y)/(y-x+1));
}
if(cmd==3)
{
double as,pfs;
as=check1(1,1,n,x,y);
pfs=check2(1,1,n,x,y);
double l=y-x+1;
double ans=pfs/l-(as/l)*(as/l);
printf("%.4lf\n",ans);
}
}
}


P3373 【模板】线段树2

题意

维护区间的乘积和加法，两个懒标记，一个为乘积因子，一个为加法因子

代码


const int maxn=200010;
int p,a[maxn],sum[4*maxn],mul[4*maxn],add[4*maxn];
inline void qm1(int k)
{

sum[ls(k)]%=p;
mul[ls(k)]%=p;
add[ls(k)]%=p;

sum[rs(k)]%=p;
mul[rs(k)]%=p;
add[rs(k)]%=p;
}
inline void build(int k,int l,int r)
{
mul[k]=1;
if(l==r)
{
sum[k]=a[l];
return ;
}
int mid=(l+r)/2;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
sum[k]=sum[ls(k)]+sum[rs(k)];
}
inline void pushdown(int k,int l,int r)
{
int mid=(l+r)/2;
sum[ls(k)]*=mul[k];
sum[rs(k)]*=mul[k];

sum[ls(k)]+=add[k]*(mid-l+1);
sum[rs(k)]+=add[k]*(r-mid);

mul[ls(k)]*=mul[k];
mul[rs(k)]*=mul[k];

add[rs(k)]=add[rs(k)]*mul[k]+add[k];
add[ls(k)]=add[ls(k)]*mul[k]+add[k];
qm1(k);
add[k]=0;
mul[k]=1;
}
inline void ADD(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&y>=r)
{
add[k]+=v;
sum[k]+=v*(r-l+1);
qm1(k);
return ;
}
pushdown(k,l,r);
int mid=(l+r)/2;
if(x<=mid)ADD(ls(k),l,mid,x,y,v);
if(y>mid)ADD(rs(k),mid+1,r,x,y,v);
sum[k]=sum[ls(k)]+sum[rs(k)];
}
inline void MUL(int k,int l,int r,int x,int y,int v)
{
if(x<=l&&y>=r)
{
add[k]*=v;//规定的规则是先加后乘，想要表示先乘后加必须要把加法标记更新
mul[k]*=v;
sum[k]*=v;
qm1(k);
return ;
}
pushdown(k,l,r);
int mid=(l+r)/2;
if(x<=mid)MUL(ls(k),l,mid,x,y,v);
if(y>mid)MUL(rs(k),mid+1,r,x,y,v);
sum[k]=sum[ls(k)]+sum[rs(k)];
}
inline int check(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)return sum[k];
pushdown(k,l,r);
int mid=(l+r)/2;
int ans=0;
if(x<=mid)ans+=check(ls(k),l,mid,x,y);
if(y>mid)ans+=check(rs(k),mid+1,r,x,y);
return ans%p;
}
main(void)
{
int n,m,cmd,x,y,k;
scanf("%lld%lld%lld",&n,&m,&p);
_1for(i,n)
{
scanf("%lld",&a[i]);
}
build(1,1,n);
_1for(j,m)
{
scanf("%lld%lld%lld",&cmd,&x,&y);
if(cmd==1)
{
scanf("%lld",&k);
MUL(1,1,n,x,y,k);
}
if(cmd==2)
{
scanf("%lld",&k);
ADD(1,1,n,x,y,k);
}
if(cmd==3)
{
printf("%lld\n",check(1,1,n,x,y)%p);
}
}
}


线段树入门到自闭