数据结构之线段树

xiaokang_suancai · 2025-07-05 14:07:06 · 个人记录

啊啊啊线段树好难qwp

算法简介

线段树是一种用于处理区间信息的二叉树。它可以支持单点修改、区间修改、区间查询操作。一般地，线段树的时间复杂度为 O(m\log n)。

算法实现

建树

在一个序列中，我们将其中的元素看作二叉树的叶子节点，然后向上构建虚拟节点，虚拟节点表示其儿子所在的区间。

如图，其中父节点的权值为其左儿子和右儿子权值之和。

我们不难看出父节点代表的区间，就是其两个子节点所在区间的集合（是这么说的吧？）就比如图中的 4 号节点所表示的区间就是它的儿子——8,9 号节点所在区间的集合。

注意：建树一般需要开 4n 大小的数组（n 为原序列长度）。

修改

我们以修改区间 [l,r] 中的元素为例。考虑朴素算法，将每个元素循环修改一次的话，时间复杂度为 O(mn)（其中 n 为元素个数，m 为操作次数），非常难受。

现在我们引入线段树的核心出装——懒惰标记（LazyTag）。~~顾名思义，它非常懒~~它的原理就是在节点上打一个标签，将操作后修改的信息存在标签上，等到下一次访问带标记的节点后再修改元素。可以结合分块思想中的懒惰标记（这篇中写的是延迟标记，一个意思）进行理解。

查询

我们以查询区间 [l,r] 中的元素为例。考虑朴素算法，将每个元素查询一遍的话，时间复杂度为 O(mn)，显然不太行。

还记得建树部分中父子节点之间的关系吗？

父节点代表的区间，就是其两个子节点所在区间的集合。

如果我们要查询区间 [l,r] 的话，我们只需要找到包括[l,r] 区间的所有节点就可以了。显然，这样的节点最多只会有 \log n 个，所以时间复杂度可以优化为 O(m \log n)。

模板题

P3372 【模板】线段树

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100005;
ll n,m,op,x,y,k,mid;
ll tree[N<<2],add[N<<2],a[N];
// tree 是线段树节点，add 是懒惰标记，a 是原序列
void build(ll x,ll l,ll r) // 建树
{
    if(l==r)
    {
        tree[x]=a[l]; // 如果是叶子节点，权值就是序列元素
        return;
    }
    ll mid=(l+r)>>1;
    build(x<<1,l,mid); // 在左子树上建树
    build((x<<1)+1,mid+1,r); // 在右子树上建树
    tree[x]=tree[x<<1]+tree[(x<<1)+1]; // 回溯时计算该节点的权值
}
void drop(ll x,ll l,ll r,ll k)
{
    add[x]+=k; // 懒惰标记对节点进行延迟修改
}
void push_down(ll x,ll l,ll r) // 下放懒惰标记
{
    ll mid=(l+r)>>1;
    drop(x<<1,l,mid,add[x]); // 向左子树下放
    drop((x<<1)+1,mid+1,r,add[x]); // 向右子树下放
    tree[x]+=(r-l+1)*add[x];  // 懒惰标记对节点进行延迟修改
    add[x]=0; // 清空懒惰标记
}
void upd(ll x,ll begin,ll end,ll l,ll r,ll k) // 修改
{
    if(begin>r||end<l) // 如果节点在区间外，直接返回
        return;
    if(begin>=l&&end<=r) // 如果在节点内，对懒惰标记进行修改
    {
        add[x]+=k;
        return;
    }
    ll mid=(begin+end)>>1;
    push_down(x,begin,end); // 下放懒惰标记
  upd(x<<1,begin,mid,l,r,k); // 修改左子树
  upd((x<<1)+1,mid+1,end,l,r,k); // 修改右子树
  tree[x]=tree[x<<1]+tree[(x<<1)+1]+(mid-begin+1)*add[x<<1]+(end-mid)*add[x<<1|1];
  // 计算该节点的权值
} 
ll query(ll x,ll begin,ll end,ll l,ll r)
{
    if(begin>r||end<l) // 跟上面一样的判断区间
        return 0;
    if(begin>=l&&end<=r)
        return tree[x]+(end-begin+1)*add[x]; // 查询区间
    ll mid=(begin+end)>>1;
    push_down(x,begin,end); // 访问的同时推懒惰标记
    return (ll)query(x<<1,begin,mid,l,r)+(ll)query((x<<1)+1,mid+1,end,l,r); // 返回区间内节点的权值之和
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        cin>>op>>x>>y;
        if(op==1)
        {
            cin>>k;
            upd(1,1,n,x,y,k);
        }
        if(op==2)
            cout<<(ll)query(1,1,n,x,y)<<endl;
    }
    return 0;
}

THE$ $END