线段树可以抽象地理解为分治思想+二叉树结构(+$lazy_tag$ 技术)。
单点修改区间查询
1 x y
:修改 $A_x$ 为 $y$。
2 x y
:询问 $x$ 到 $y$ 之间的最大值。
$\text{step1.}$ 建树
使用结构体存储线段树的每一个结点。结构体中三个变量分别表示结点的最值或总和、包含区间的左右端点。
注意线段树结构体需要开 $4$ 倍,即 $N\times4$。下面说明原因。假设有一棵处理 $n$ 个元素的线段树,且只有一个元素 $t$ 存储在最后一层,其他层都是满的。如果用满二叉树存储,最后一层有 $2n$ 个结点,却只有一个结点存储元素,其他都浪费了。倒数第二层是满的,有 $n$ 个结点。所有层加起来,共有 $1+2+4+\cdots+n+2n=2n\times2-1\approx4n$ 个结点。
接着递归建立左右子树。假设当前结点编号为 $p$ ,则左子树编号为 $p\times2$,右子树编号为 $p\times2+1$。假设当前结点包含区间为 $[l,r]$,则左子树区间为 $[l,mid]$,右子树区间为 $[mid+1,r]$。
递归到子结点后标记子结点的区间和或区间最值并开始返回。递归返回意味着左右子树已计算好,所以在递归返回的过程中更新每个区间的区间和或区间最值。
$\text{step2.}$ 单点修改
从父结点向下递归直到要修改的结点,返回的一路上更新结点的值,因为递归路上遇到的结点都包含要修改的结点。
$\text{step3.}$ 区间查询
如果查询区间覆盖了整个结点,则直接返回结点的区间总和或最值。
否则递归左右子树,直到查询区间覆盖整个结点,返回时再左右子树求和或求最值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
const int N=100100;
int n,a[N],m,x,y,op;
struct node
{
int cl,cr,val;
}c[N*4];//线段树数组开4倍
void build(int k,int l,int r)//建立线段树 k:当前结点的编号 l:当前结点包含区间的左端点 r:当前结点包含区间的右端点
{
int mid=(l+r)/2;
c[k].cl=l,c[k].cr=r;
if(l==r)//当前结点是子结点
{
c[k].val=a[l];
return;
}
build(k*2,l,mid);//建立左子树,把区间的左半部分分给左子树
build(k*2+1,mid+1,r);//建立右子树,把区间的右半部分分给右子树
c[k].val=max(c[k*2].val,c[k*2+1].val);//建立左右子树后,计算当前结点的区间最大值
}
void add(int k,int p,int num)//单点修改 k:当前结点 p:要修改的位置 x:要修改的值
{
if(c[k].cl==c[k].cr&&c[k].cl==p)//当前结点是要修改的位置
{
c[k].val=num;
return;
}
if(p<=c[k*2].cr) add(k*2,p,num);//要找的结点在左子树的区间
else add(k*2+1,p,num);//要找的结点在右子树的区间
c[k].val=max(c[k*2].val,c[k*2+1].val);//更新
}
int ma(int k,int l,int r)//区间查询 k:当前结点编号 l:查询区间的左端点 r:查询区间的右端点
{
int ans=INT_MIN;
if(l<=c[k].cl&&r>=c[k].cr) return c[k].val;//要查询的区间包含了整个当前区间
if(l<=c[k*2].cr) ans=max(ans,ma(k*2,l,r));//要查询的区间包含当前结点左子树的区间
if(r>=c[k*2+1].cl) ans=max(ans,ma(k*2+1,l,r));//要查询的区间包含当前结点右子树的区间
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
build(1,1,n);//建树
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1) add(1,x,y);//单点修改
else
{
if(x>y) swap(x,y);
printf("%d\n",ma(1,x,y));//区间查询
}
}
return 0;
}
区间修改区间查询(需要运用 $lazy_tag$ 技术)
1 x y k
:将区间 $[x,y]$ 内每个数加上 $k$。
2 x y
:输出区间 $[x,y]$ 内每个数的和。
$\text{step1.}$ 建树
同单点修改区间查询。
$\text{step2.}$ 给结点打 $lazy_tag$ 标记
我们可以定义一个 $tag[i]$,用它统一记录结点 $i$ 区间的修改,而不是一个个递归修改每一个元素。
先赋值 $tag[i]$ 表示第 $i$ 个结点区间每个元素要做的修改,接着更新结点 $i$ 的总和,结点 $i$ 的总和应加上 $(y-x+1)\times k$。
使用 $lazy_tag$ 方法时,若修改的是一个线性区间,就只对这个线性区间进行整体修改(打标记),其内部每个元素的内容先不作修改,只有当这个线段区间的一致性被破坏时,才把标记传递给左右子树。
$\text{step3.}$ 标记下放
标记下放是处理 $lazy_tag$ 的一个技巧。在进行多次区间修改时,一个结点需要记录多个区间修改,而这些区间修改往往有冲突。
例如,进行 $[4,9]$ 和 $[5,8]$ 两个区间的修改,它们都会影响到 $[4,5]$ 这个结点。由于修改区间 $[4,9]$ 完全覆盖结点 $[4,9]$,所以用 $[4,5]$ 这个结点打了标记。当修改 $[5,8]$ 时,修改区间 $[5,8]$ 无法完全覆盖结点 $[4,5]$,于是递归到左子树 $[5,5]$,这时 $[5,5]$ 能被完全覆盖,但是如果打 $[5,5]$ 结点的标记,就会破坏到结点 $[4,5]$ 打的标记。此时结点 $[4,5]$ 就不得不把标记传给左右子树,传递后 $[4,5]$ 结点的标记应当清空。
总而言之,标记下放的过程如下:首先看结点 $i$ 的 $tag[i]$ 是否有值,若无值,说明结点 $i$ 没有打标记,不需要下放,直接 return
。接下来就把 $tag[i]$ 传给左右子树,然后把 $tag[i]$ 清零。
$\text{step4.}$ 区间修改
如果修改区间覆盖整个结点区间,则直接对这个结点打标记,不用再递归了。
否则标记下放,并递归左右子树直到整个结点区间被覆盖。递归返回的一路上更新区间总和。
$\text{step5.}$ 区间查询
同单点修改区间查询,但是查询区间无法完全覆盖结点区间时,要给结点标记下放。
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+100;
int n,m,op,x,y;
ll tag[N*4],a[N],k;//tag[i]为第i个结点的lazy_tag,统一记录这个结点区间的修改
struct node
{
ll val;
int tl,tr;
}b[N*4];//线段树数组开4倍
//建树
void build(int p,int l,int r)//p:当前结点 l:当前结点包含区间的左端点 r:当前结点包含区间的右端点
{
int mid=(l+r)/2;
tag[p]=0;//初始化lazy_tag
b[p].tl=l,b[p].tr=r;//记录结点p包含区间的左右端点
if(l==r)//结点p是子结点
{
b[p].val=a[l];
return;
}
//建立左右子树
build(p*2,l,mid);
build(p*2+1,mid+1,r);
b[p].val=b[p*2].val+b[p*2+1].val;//更新结点p包含区间的总和
}
//给结点p打标记
void add_tag(int p,ll num)//p:结点编号 num:结点p区间每个数要加的数
{
tag[p]+=num;//给结点p打lazy_tag
b[p].val+=num*(b[p].tr-b[p].tl+1);//更新结点p区间总和
}
//标记下放(把lazy_tag传给子树)
void push_down(int p)//p:结点编号
{
if(!tag[p]) return;//结点p没有打过lazy_tag
//把lazy_tag传给左右子树
add_tag(p*2,tag[p]);
add_tag(p*2+1,tag[p]);
tag[p]=0;//传给子树后清空结点p的lazy_tag
}
//区间修改
void update(int p,int l,int r,ll num)//p:当前结点 区间修改:把区间[l,r]每个数加上num
{
int mid=(b[p].tl+b[p].tr)/2;
if(l<=b[p].tl&&r>=b[p].tr)//修改的区间完全覆盖结点p的区间
{
add_tag(p,num);//直接给结点p打标记
return;//无需再递归子树了
}
push_down(p);//无法完全覆盖,把结点p打过的lazy_tag下放
if(l<=mid) update(p*2,l,r,num);//修改区间包含结点p的左子树,递归
if(r>mid) update(p*2+1,l,r,num);//修改区间包含结点p的右子树,递归
b[p].val=b[p*2].val+b[p*2+1].val;//更新结点p区间的总和
}
//区间查询
ll query(int p,int l,int r)//p为当前结点,[l,r]是查询的区间
{
int mid=(b[p].tl+b[p].tr)/2;
ll sum=0;
if(l<=b[p].tl&&r>=b[p].tr) return b[p].val;//查询区间完全覆盖结点p区间,直接返回
push_down(p);//否则给结点p标记下放
if(l<=mid) sum+=query(p*2,l,r);//修改区间包含结点p的左子树
if(r>mid) sum+=query(p*2+1,l,r);//修改区间包含结点p的右子树
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);//建树
while(m--)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
scanf("%lld",&k);
update(1,x,y,k);
}
else printf("%lld\n",query(1,x,y));
}
return 0;
}