线段树基本操作

MinimumSpanningTree · 2023-12-30 14:47:45 · 算法·理论

线段树可以抽象地理解为分治思想+二叉树结构（+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：要修改的位置 num：要修改的值
{
    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,5]，所以用 [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;
}