【数据结构】线段树

CR400BF_1145 · 2025-11-28 18:31:49 · 算法·理论

要想进行区间查询，我们可以使用前缀和。要想处理区间修改，我们可以使用差分。然而，如果我们需要同时进行区间查询与修改，这两种算法都无法高效地解决问题。

此时，我们就需要一种数据结构——线段树来帮助我们，它可以以 \mathcal{O}(\log n) 的时间复杂度处理这两种操作。

约定

本文中的代码仅作为示范，请根据题目实际情况选择合适的数据类型与数组大小。

简介

线段树是一种专门用来处理区间问题的数据结构，一般是完全二叉树。它基于分治思想将原序列递归地进行划分，处理并记录各个子区间的信息。查询时，我们将目标区间分解为 \mathcal{O}(\log n) 个子区间，将子区间中的信息整合起来，就得到了目标区间的信息。

::cute-table	40	<	<	<	<	<	<
21	<	<	<	19	<	<	<
9	<	12	<	11	<	8	<
1	8	3	9	7	4	2	6

这是一棵维护区间和的线段树示例。最底层的就是原序列，它向上结合出了不同的子节点。

假设要查询区间 [3,7] 的区间和，我们只需要访问如下节点进行查询。

::cute-table	40	<	<	<	<	<	<
21	<	<	<	19	<	<	<
9	<	12	<	11	<	8	<
1	8	3	9	7	4	2	6

线段树一般占用 \mathcal{O}(n) 的空间，实际多开 4n 大小，具体原因见 OI-Wiki。

由于目标区间由子区间的信息组合而成，线段树通常只用于维护符合结合律的操作。

建树

以维护区间和为例，我们首先需要建立线段树。可以考虑先从顶部出发向下直到底部，然后递归自底向上地建树。

首先，我们定义结构体node。

struct node
{
    long long data,lazy=0;
}tree[400060];

里面的data就是该节点存储的数据，lazy的含义之后会讲。

接下来为了简洁，我们实现一个函数pushup(idx)，它通过其子节点的信息维护当前节点的信息。

void pushup(int idx)
{
    tree[idx].data=tree[idx<<1].data+tree[idx<<1|1].data;
    return;
}

函数中，idx<<1是左孩子，idx<<1|1是右孩子。由于左移之后二进制的个位肯定是 0，我们将idx<<1按位或 1 其实就相当于将其加上一。

然后，我们实现建树函数build(l,r,idx)。如果区间的长度为 1，就表明已经到了最底层，将信息直接写入（即构建叶子节点）并开始返回。否则，递归到左右两侧的子树中，待两侧子树构建完毕再维护当前节点。

void build(int l,int r,int idx)
{
    if(l==r)
    {
        tree[idx].data=a[l];
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,idx<<1);
    build(mid+1,r,idx<<1|1);
    pushup(idx);
    return;
}

建树的操作是 \mathcal{O}(n) 的。在构建线段树时，我们通常这样调用它。

build(1,n,1);

此时，idx中填写的就是根节点的编号，也就是 1。如果你实现了以 0 为根节点编号的线段树，你就应该调用build(0,n-1,0)，但并不推荐这样做。

更新

我们首先实现更新，不过区间更新操作是有很多种类型的，我们这里先假设更新就是给区间 [L,R] 中的每个元素加上 k。对于当前的区间 [l,r]，我们有三种情况。

对于第一种情况，我们直接返回就行了，不需要执行任何操作。第二种情况，如果更新到了叶子节点，我们就对其进行更新并返回，否则继续递归，不然下面的节点没有更新到，会出现数据不一致。最后一种情况，我们也继续递归，并在递归完成后进行pushup()操作。

void update(int L,int R,int l,int r,int idx,long long k)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        if(l==r)
        {
            tree[idx].data+=k;
            return;
        }
    }
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,idx<<1,k);
    update(L,R,mid+1,r,idx<<1|1,k);
    pushup(idx);
    return;
}

查询

实现了建树与更新后，我们处理查询。我们需要实现query(L,R,l,r,idx)，它负责查询目标区间 [L,R] 的信息。

同样有三种情况，这里不再列出。对于第一种情况，我们返回一个对结果无影响的值，这里是 0（因为 0 对区间和没有影响。如果是维护区间最大值，可以返回INT_MIN等）。第二种情况，我们直接返回当前节点的信息。最后一种情况，我们进行递归，将递归函数返回的值相加并返回。

long long query(int L,int R,int l,int r,int idx)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[idx].data;
    int mid=l+((r-l)>>1);
    return query(L,R,l,mid,idx<<1)+query(L,R,mid+1,r,idx<<1|1);
}

懒惰标记

我们成功实现了一棵线段树。然而，它的效率并不如预期，没有通过 P3372。

我们发现在更新时，当前的代码会直接更新到叶子节点。然而，底部的一些节点在之后的查询中可能并没有被访问，这不就白更新了吗？这下，我们在结构体中声明的lazy就有用了。我们可以将修改操作的变化值存储在lazy中，只在必要时才将lazy下发给子节点并真正更新当前节点。由于这可以说是“懒得更新之后的节点”，它被称为懒惰标记。

我们首先实现pushdown(idx,l,r)，它负责处理当前节点的懒惰标记，并将其下发到子节点。

void pushdown(int idx,int l,int r)
{
    if(!tree[idx].lazy) return;
    int mid=l+((r-l)>>1);
    tree[idx<<1].lazy+=tree[idx].lazy,tree[idx<<1|1].lazy+=tree[idx].lazy;
    tree[idx<<1].data+=tree[idx].lazy*(mid-l+1),tree[idx<<1|1].data+=tree[idx].lazy*(r-mid);
    tree[idx].lazy=0;
    return;
}

为什么还要传入当前区间呢？很简单，因为懒惰标记中存储的是区间中每个元素的增量，必须乘上区间长度才能得到区间增量。

接下来，我们在处理查询与更新操作时，如果需要向下递归，先pushdown()即可处理懒惰标记。然后，对于更新操作中的第二种情况，我们可以高效地解决而不必再继续递归。

void update(int L,int R,int l,int r,int idx,long long k)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        tree[idx].data+=k*(r-l+1),tree[idx].lazy+=k;
        return;
    }
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,idx<<1,k);
    update(L,R,mid+1,r,idx<<1|1,k);
    pushup(idx);
    return;
}

到此，我们成功写出了一棵线段树。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005];
struct node
{
    long long data,lazy=0;
}tree[400060];
void pushup(int idx)
{
    tree[idx].data=tree[idx<<1].data+tree[idx<<1|1].data;
    return;
}
void pushdown(int idx,int l,int r)
{
    if(!tree[idx].lazy) return;
    int mid=l+((r-l)>>1);
    tree[idx<<1].lazy+=tree[idx].lazy,tree[idx<<1|1].lazy+=tree[idx].lazy;
    tree[idx<<1].data+=tree[idx].lazy*(mid-l+1),tree[idx<<1|1].data+=tree[idx].lazy*(r-mid);
    tree[idx].lazy=0;
    return;
}
void build(int l,int r,int idx)
{
    if(l==r)
    {
        tree[idx].data=a[l];
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,idx<<1);
    build(mid+1,r,idx<<1|1);
    pushup(idx);
    return;
}
long long query(int L,int R,int l,int r,int idx)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[idx].data;
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    return query(L,R,l,mid,idx<<1)+query(L,R,mid+1,r,idx<<1|1);
}
void update(int L,int R,int l,int r,int idx,long long k)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        tree[idx].data+=k*(r-l+1),tree[idx].lazy+=k;
        return;
    }
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,idx<<1,k);
    update(L,R,mid+1,r,idx<<1|1,k);
    pushup(idx);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    for(int i=1,cz,x,y;i<=m;i++)
    {
        cin>>cz>>x>>y;
        if(cz==1)
        {
            long long k;
            cin>>k;
            update(x,y,1,n,1,k);
        }
        else cout<<query(x,y,1,n,1)<<endl;
    }
    return 0;
}

不同类型的区间更新

除了全都加上 k，还有许多其他常见的区间更新方式。

区间乘法

如果我们的修改操作是将区间中的元素乘上 k，相应的处理就需要改变。不过单纯的区间乘法很简单，只需要注意两点。

必须将lazy初始化为 1。
在update()、pushdown()时直接乘上 k 就行了，区间乘法的更新对区间长度并没有需求。

代码就不放了，很简单。

直接修改

如果修改操作直接将区间中的元素修改为 k，我们可以让懒惰标记直接表示当前需要修改的值。不过这会导致无法通过将懒惰标记设为诸如 0 的值来表明没有操作。所以，我们可以额外在结构体中定义一个bool变量来表示当前节点是否有待更新的懒惰标记。

struct node
{
    long long data,lazy=0;
    bool have=false;
}tree[400060];

相应的pushdown()函数如下。

void pushdown(int idx,int l,int r)
{
    if(!tree[idx].have) return;
    int mid=l+((r-l)>>1);
    tree[idx<<1].lazy=tree[idx<<1|1].lazy=tree[idx].lazy;
    tree[idx<<1].data=tree[idx].lazy*(mid-l+1),tree[idx<<1|1].data=tree[idx].lazy*(r-mid);
    tree[idx<<1].have=tree[idx<<1|1].have=true;
    tree[idx].have=false;
    return;
}

update()函数同理，就不放出来了。

混合修改

在 P3373 中，我们需要同时处理区间加、乘法并对某个模数取模。我们可以给加法、乘法各开一个单独的懒惰标记。

struct node
{
    long long data,add=0,mul=1;
}tree[400060];

不过这会导致一个问题——在下传懒惰标记时，是先处理加法还是乘法的懒惰标记呢？

不妨设 \text{mul}_x 表示节点 x 的乘法懒惰标记，\text{add}_x 表示节点 x 的加法懒惰标记，\text{data}_{x} 表示节点 x 当前维护的区间和。我们先看当前节点 x 的左孩子。如果先加后乘，新的 \text{data}_{2x} 就会变成

&\text{mul}_x[\text{mul}_{2x}(\text{data}_{2x}+\text{add}_{2x})+\text{add}_x]\\ &=\text{mul}_x(\text{mul}_{2x}\text{data}_{2x}+\text{mul}_{2x}\text{add}_{2x}+\text{add}_x)\\ &=\text{mul}_x\text{mul}_{2x}\text{data}_{2x}+\text{mul}_x\text{mul}_{2x}\text{add}_{2x}+\text{mul}_x\text{add}_x\\ &=\text{mul}_x\text{mul}_{2x}(\text{data}_{2x}+\text{add}_{2x}+\frac{\text{add}_x}{\text{mul}_{2x}}) \end{aligned}

所以，新的 \text{add}_{2x} 会变成 \text{add}_{2x}+\frac{\text{add}_x}{\text{mul}_{2x}}。这是不可取的，因为它涉及除法，会出现精度丢失。我们必须先乘后加。

&(\text{data}_{2x}\text{mul}_{2x}+\text{add}_{2x})\text{mul}_x+\text{add}_x\text{len}\\ &=\text{data}_{2x}(\text{mul}_{2x}\text{mul}_x)+(\text{add}_{2x}\text{mul}_x+\text{add}_x\text{len}) \end{aligned}

其中 \text{len} 表示当前区间长度。

也就是说，新的 \text{mul}_{2x} 是 \text{mul}_{2x}\text{mul}_x，新的 \text{add}_{2x} 是 \text{add}_{2x}\text{mul}_x+\text{add}_x，完全可以。注意，这里 \text{add}_x 并没有乘上 \text{len}，因为它表示的是区间中每个元素的待加量，而不是整个区间的。

void pushdown(int idx,int l,int r)
{
    if(tree[idx].mul==1&&!tree[idx].add) return;
    int mid=l+((r-l)>>1);
    tree[idx<<1].data=(tree[idx<<1].data*tree[idx].mul%MOD+tree[idx].add*(mid-l+1)%MOD)%MOD;
    tree[idx<<1].mul=tree[idx<<1].mul*tree[idx].mul%MOD;
    tree[idx<<1].add=(tree[idx<<1].add*tree[idx].mul%MOD+tree[idx].add)%MOD;
    tree[idx<<1|1].data=(tree[idx<<1|1].data*tree[idx].mul%MOD+tree[idx].add*(r-mid)%MOD)%MOD;
    tree[idx<<1|1].mul=tree[idx<<1|1].mul*tree[idx].mul%MOD;
    tree[idx<<1|1].add=(tree[idx<<1|1].add*tree[idx].mul%MOD+tree[idx].add)%MOD;
    tree[idx].add=0,tree[idx].mul=1;
    return;
}

当然，在pushdown()里，处理乘法、加法懒惰标记的代码顺序没有什么关系。

在区间乘法更新时，我们只需要给区间中的数据以及加法、乘法懒惰标记都乘上 k 就行了。

#include<bits/stdc++.h>
using namespace std;
int n,q;
long long MOD,a[100005];
struct node
{
    long long data,add=0,mul=1;
}tree[400060];
void pushup(int idx)
{
    tree[idx].data=(tree[idx<<1].data+tree[idx<<1|1].data)%MOD;
    return;
}
void pushdown(int idx,int l,int r)
{
    if(tree[idx].mul==1&&!tree[idx].add) return;
    int mid=l+((r-l)>>1);
    tree[idx<<1].data=(tree[idx<<1].data*tree[idx].mul%MOD+tree[idx].add*(mid-l+1)%MOD)%MOD;
    tree[idx<<1].mul=tree[idx<<1].mul*tree[idx].mul%MOD;
    tree[idx<<1].add=(tree[idx<<1].add*tree[idx].mul%MOD+tree[idx].add)%MOD;
    tree[idx<<1|1].data=(tree[idx<<1|1].data*tree[idx].mul%MOD+tree[idx].add*(r-mid)%MOD)%MOD;
    tree[idx<<1|1].mul=tree[idx<<1|1].mul*tree[idx].mul%MOD;
    tree[idx<<1|1].add=(tree[idx<<1|1].add*tree[idx].mul%MOD+tree[idx].add)%MOD;
    tree[idx].add=0,tree[idx].mul=1;
    return;
}
void build(int l,int r,int idx)
{
    if(l==r)
    {
        tree[idx].data=a[l]%MOD;
        return;
    }
    int mid=l+((r-l)>>1);
    build(l,mid,idx<<1);
    build(mid+1,r,idx<<1|1);
    pushup(idx);
    return;
}
long long query(int L,int R,int l,int r,int idx)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[idx].data%MOD;
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    return (query(L,R,l,mid,idx<<1)+query(L,R,mid+1,r,idx<<1|1))%MOD;
}
void update(int L,int R,int l,int r,int idx,long long k,bool ismul)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        if(ismul)
        {
            tree[idx].data=tree[idx].data*k%MOD;
            tree[idx].add=tree[idx].add*k%MOD;
            tree[idx].mul=tree[idx].mul*k%MOD;
        }
        else
        {
            tree[idx].data=(tree[idx].data+k*(r-l+1))%MOD;
            tree[idx].add=(tree[idx].add+k)%MOD;
        }
        return;
    }
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,idx<<1,k,ismul);
    update(L,R,mid+1,r,idx<<1|1,k,ismul);
    pushup(idx);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q>>MOD;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    for(int i=1,cz,x,y;i<=q;i++)
    {
        cin>>cz>>x>>y;
        if(cz==1)
        {
            long long k;
            cin>>k;
            update(x,y,1,n,1,k,true);
        }
        else if(cz==2)
        {
            long long k;
            cin>>k;
            update(x,y,1,n,1,k,false);
        }
        else cout<<query(x,y,1,n,1)<<endl;
    }
    return 0;
}

动态开点线段树

我们知道，线段树进行一次更新操作的时间复杂度是 \mathcal{O}(\log n)，也就是最多访问到 \mathcal{O}(\log n) 个节点。不妨设有 m 次操作，则实际最多访问到的节点数量为 \mathcal{O}(m\log n)，其余的节点就没有必要建出来了。像这样只建立被访问到的节点的线段树，称为动态开点线段树。不过这样就会导致我们无法用 2n 与 2n+1 来表示左右孩子，因此我们必须在结构体中对其进行记录。如果没有左右孩子，用 0 表示。

struct node
{
    long long data,lazy=0;
    int left=0,right=0;
}tree[400060];

由于需要动态开点，原本的build()已经不再适用。现在，对于每个新的输入，我们都进行一次单点更新。这样做的时间复杂度是 \mathcal{O}(n\log n)。如果你采用和普通线段树一样的建树方式，最后就会把整棵树全都建出来，也就失去了动态开点的意义。

每次进行pushdown()操作时，我们都检查当前节点的子节点。如果没有，就创建它。其他的地方，动态开点线段树则几乎与普通线段树别无二致。

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
long long a[100005];
struct node
{
    long long data,lazy=0;
    int left=0,right=0;
}tree[400060];
int newnode()
{
    tree[++cnt]={0,0,0,0};
    return cnt;
}
void pushup(int idx)
{
    tree[idx].data=tree[tree[idx].left].data+tree[tree[idx].right].data;
    return;
}
void pushdown(int idx,int l,int r)
{
    if(!tree[idx].lazy) return;
    if(!tree[idx].left) tree[idx].left=newnode();
    if(!tree[idx].right) tree[idx].right=newnode();
    int mid=l+((r-l)>>1);
    tree[tree[idx].left].data+=tree[idx].lazy*(mid-l+1);
    tree[tree[idx].left].lazy+=tree[idx].lazy;
    tree[tree[idx].right].data+=tree[idx].lazy*(r-mid);
    tree[tree[idx].right].lazy+=tree[idx].lazy;
    tree[idx].lazy=0;
    return;
}
long long query(int L,int R,int l,int r,int idx)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[idx].data;
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    return query(L,R,l,mid,tree[idx].left)+query(L,R,mid+1,r,tree[idx].right);
}
void update(int L,int R,int l,int r,int idx,long long k)
{
    if(l>R||r<L) return;
    if(l>=L&&r<=R)
    {
        tree[idx].data+=k*(r-l+1),tree[idx].lazy+=k;
        return;
    }
    pushdown(idx,l,r);
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,tree[idx].left,k);
    update(L,R,mid+1,r,tree[idx].right,k);
    pushup(idx);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    newnode();
    for(int i=1;i<=n;i++) cin>>a[i],update(i,i,1,n,1,a[i]);
    for(int i=1,cz,x,y;i<=m;i++)
    {
        cin>>cz>>x>>y;
        if(cz==1)
        {
            long long k;
            cin>>k;
            update(x,y,1,n,1,k);
        }
        else cout<<query(x,y,1,n,1)<<endl;
    }
    return 0;
}

标记永久化

在前面，我们采用pushdown()对懒惰标记进行下传。但对于懒惰标记的处理，实际上还有另一种方法——标记永久化。相比于下传的方法，标记永久化的常数会更小。如它的名字，懒惰标记一旦打上就再也不会消失，而是在查询与更新操作中直接计算。

更具体的，在标记永久化中，我们不再进行pushdown()操作。我们依旧有之前的三种情况。对于情况二，就表明当前区间内所有子节点都受到了修改，可以直接打上懒惰标记，修改data并返回。对于情况三，只有一部分节点需要修改，我们不能直接修改当前节点的懒惰标记，于是只能修改data，并继续向下递归处理子节点。

查询时，我们需要累加路径上所有节点的懒惰标记，才能计算出当前区间的真实值。

long long query(int L,int R,int l,int r,int idx,long long t)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return tree[idx].data+t*(r-l+1);
    int mid=l+((r-l)>>1);
    return query(L,R,l,mid,idx<<1,t+tree[idx].lazy)+query(L,R,mid+1,r,idx<<1|1,t+tree[idx].lazy);
}
void update(int L,int R,int l,int r,int idx,long long k)
{
    if(l>R||r<L) return;
    tree[idx].data+=k*(min(R,r)-max(L,l)+1);
    if(l>=L&&r<=R)
    {
        tree[idx].lazy+=k;
        return;
    }
    int mid=l+((r-l)>>1);
    update(L,R,l,mid,idx<<1,k);
    update(L,R,mid+1,r,idx<<1|1,k);
    return;
}