线段树（basic）

prediction

2026-09-05 10:09:35

发布于：浙江

38阅读

0回复

0点赞

讲的就是题目啊。

知识概括

线段树是一种树形结构，用分治的思想，把数组里的元素建成二叉树，用于快速查询区间和和区间修改之类的操作。

它的修改（单点或区间）和区间查询时间复杂度都是 $O(\log n)$ ，但是，如果数组元素少或者操作次数少的时候没必要用这个，如果说是这种题的数据，那么我们就要使用线段树来解。

正题

如果你学过归并排序或者其他的分治思想技巧，那么你肯定知道分治就是把东西给分成多份去递归求解，线段树也是一样，左儿子管区间的左半部分，右儿子管区间的右半部分。当然，如果 $l=r$ 的话，说明这个节点直接存 $a[l]$ 的值。

比如说 $1-8$ 的升序排列，线段树里的东西大概就是

OI里我们常常用数组存这个树结构，根的编号就是 $1$ ，一个节点 $x$ 的左右儿子是 $2x$ 与 $2x+1$ ，相信大家都知道，那为啥你去看所有的线段树题解，他们的 $tree$ 数组都要开 $MAXN*4$ 呢？

举个例子， $1、2、3、4、5$ ，它们是数组里的元素，画一画就知道，线段树有 $9$ 个节点，而线段树会把区间补到大于等于 $n$ （这里 $n=5$ ）的最小的 $2$ 的幂，这里记为 $size$ ，那么 $size$ 满足 $size ≥ n$ 且有 $size = 2^k$ ，这一颗虚拟的满二叉树的节点数量就是 $2*size-1$ 。

看下最坏情况：

$2^{k-1}+1 < n ≤ 2^k$

设 $n=2^{k-1}+1$ ，此时 $size=2^k$ ，总结点上限是：

$2\cdot size -1 = 2\cdot 2^k-1 =2^{k+1} -1$

但我们有 $n>2^{k-1}$ ，所以 $2^k<2n$ ，也有 $2^{k+1}<4n$ 。

至此，我们知道了线段树节点数量 $<4n$ 。

线段树1.0

这个是简单的线段树，只需要实现单点修改和区间求和，虽然说听着挺难的，但是我们看下实现就能发现，hjda，嗯对。~~（不是我说的我是区）~~

看下建树吧。

递归函数 $build(u,l,r)$ ，代表节点 $u$ 管 $l-r$ 这个区域

如果 l==r 赋值 a[l]

mid=(l+r)>>1;

build(u*2,l,mid);//建左子树
build(u*2+1,mid+1,r);//建右子树

u=u*2+u*2+1;//简写，就是合并左右子树的值（计算这个区间的和）

然后是单点修改。

名字叫update(u,l,r,pos,val)

if l==r u=val;return;//直接赋值

mid=(l+r)>>1;
if pos<=mid //改左子树
else //改右子树

pushup(u);//改完儿子更新父亲

你可以发现我们连赋值都是分治的，好美丽的线段树。

最后是区间求和。

名字是query(u,l,r,L,R)

if 不相交 return 0;//无贡献
if 完全相交 return u;//返回的是u区间的和

mid=(l+r)>>1;

return 左边+右边//这个区间的

又是分治递归，线段树你咋这么好看😍。

完整实现：

typedef long long ll;
const long long MAXN=100005;//线段树开4倍空间
ll tree[MAXN*4];
ll lazy[MAXN*4];//别管这个数组
ll a[MAXN];
int n, m;
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}
void pushdown(int p,int l,int r)
{
    if(lazy[p]==0)  return;
    int ls=p*2, rs=p*2+1;
    ll add=lazy[p];
    int mid=(l+r)/2;
    tree[ls]+=add*(mid-l+1);
    lazy[ls]+=add;//打标记
    tree[rs]+=add*(r-mid);
    lazy[rs]+=add;//打标记
    lazy[p]=0;//清空自己的标记
}
void update(int p,int l,int r,int L,int R,ll val)
{
    if(L<=l&&r<=R)
    {
        tree[p]+=val*(r-l+1);//区间总和加上val乘区间长
        lazy[p]+=val;//记录延迟增量
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(L<=mid) update(p*2,l,mid,L,R,val);
    if(R>mid) update(p*2+1,mid+1,r,L,R,val);
    tree[p]=tree[p*2]+tree[p*2+1];
}
ll query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tree[p];
    pushdown(p,l,r);
    int mid=(l+r)/2;
    ll res=0;
    if(L<=mid) res+=query(p*2,l,mid,L,R);
    if(R>mid) res+=query(p*2+1,mid+1,r,L,R);
    return res;
}

然后你就可以用这个简单的线段树过了P3372 【模板】线段树 1。

这就是简单的线段树。

P2357 守墓人

主要就是处理更新主墓碑，可以看成一个单点修改，然后减 $k$ 就是加 $-k$ ，所以仍然是那个板子，多处理几个操作就过了。

typedef long long ll;
const ll MAXN=2e5+5;//线段树开4倍空间
ll tree[MAXN*4];
ll lazy[MAXN*4];
ll a[MAXN];
int n, m;
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=tree[p*2]+tree[p*2+1];
}
void pushdown(int p,int l,int r)
{
    if(lazy[p]==0)  return;
    int ls=p*2, rs=p*2+1;
    ll add=lazy[p];
    int mid=(l+r)/2;
    tree[ls]+=add*(mid-l+1);
    lazy[ls]+=add;//打标记
    tree[rs]+=add*(r-mid);
    lazy[rs]+=add;//打标记
    lazy[p]=0;//清空自己的标记
}
void update(int p,int l,int r,int L,int R,ll val)
{
    if(L<=l&&r<=R)
    {
        tree[p]+=val*(r-l+1);//区间总和加上val乘区间长
        lazy[p]+=val;//记录延迟增量
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(L<=mid) update(p*2,l,mid,L,R,val);
    if(R>mid) update(p*2+1,mid+1,r,L,R,val);
    tree[p]=tree[p*2]+tree[p*2+1];
}
ll query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tree[p];
    pushdown(p,l,r);
    int mid=(l+r)/2;
    ll res=0;
    if(L<=mid) res+=query(p*2,l,mid,L,R);
    if(R>mid) res+=query(p*2+1,mid+1,r,L,R);
    return res;
}
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,1,n);//建区间1~n
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x, y;
            ll k;
            cin>>x>>y>>k;
            update(1,1,n,x,y,k);
        }
        else if(op==2)
        {
            int k;
            cin>>k;
            update(1,1,n,1,1,k);
        }
        else if(op==3)
        {
            int k;
            cin>>k;
            update(1,1,n,1,1,-k);
        }
        else if(op==4)
        {
            int x, y;
            cin>>x>>y;
            ll ans=query(1,1,n,x,y);
            cout<<ans<<"\n";
        }
        else
        {
            cout<<query(1,1,n,1,1)<<'\n';
        }
    }
}

P1816 忠诚

查询实现题，连修改都不用。

其实就是把区间和的板子改了，每次的 $tr[u]$ 取它左右子树里的最小值即可。

const int MAXN=1e5+5;
int tr[MAXN*4];
int a[MAXN];
int m, n;
void build(int p,int l,int r)
{
    if(l==r)
    {
        tr[p]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tr[p]=min(tr[p*2],tr[p*2+1]);
}
int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tr[p];
    int mid=(l+r)/2;
    int res=0x3f3f3f3f;
    if(L<=mid) res=min(res,query(p*2,l,mid,L,R));
    if(R>mid) res=min(res,query(p*2+1,mid+1,r,L,R));
    return res;
}
int main()
{
    cin>>m>>n;
    for(int i = 1;i<=m;i++) cin>>a[i];
    build(1,1,m);
    while(n--)
    {
        int l, r;
        cin>>l>>r;
        cout<<query(1,1,m,l,r)<<" ";
    }
}

~~线段树2.0~~

你其实也在代码里看到了一个 $lazy$ ，这就是二代线段树的重中之重，懒标记。

都说了懒标记了，线段树就先放一下啊。

懒标记

我们知道线段树的单点修改时间是 $O(\log n)$ 的，如果我们要做区间修改，那么最坏情况下只能给每一个区间内的元素做单点修改，时间 $O(n)$ ，大数据直接T飞。

这个时候懒标记就有用了，这个东西的核心思想就是 能不用就不用 ，也就是把标记先存在父节点上，等要用的时候再下传给子节点，这样拖延修改后，时间又回到了 $O(\log n)$ 。

我们在线段树里把懒标记数组标为 $lazy$ ， $lazy[u]$ 代表节点 $u$ 代表的整个区间已经完成区间加，但是未更新左右儿子的值。

你在之前看到的 $pushdown$ 函数，其实就是下传懒标记用的。（你为啥现在才说？）

算了来讲这个函数吧。

函数有 $3$ 步：

如果这个节点无懒标记，那么就返回。
将父节点的修改加到左右儿子身上，更新现在的左右儿子的区间，同时给左右儿子也打懒标记。
将自己的懒标记清空，代表这个懒标记已经打给儿子们了，不用再继续下传。

都说到这里了，来说下 $pushdown$ 和 $pushup$ 的区别， $pushdown$ 就是把懒标记下传，是 fa→son ，而 $pushup$ 是更新父亲的区间值（合并区间），是 son→fa 。

讲完函数了。

说下啥时候要用 $pushdown$ 。

在 修改、查询 的时候要用。

修改时，如果当前区间被完全覆盖，直接返回，如果不是就先改掉左右儿子，就是 $pushdown$ ，最后 $pushup$ 合并区间。

查询也是如此，下传懒标记后递归返回左儿子加右儿子的值。

好啦，花开两朵，一支表完了。

回到线段树。

线段树2.0

有了对懒标记的了解，想必你一定知道该怎么写 P3373 【模板】线段树 2 了，那么就来写吧。

我们需要维护加乘查询 $3$ 个操作，哎呀加写过了，查询也是，不讲，来讲讲乘。

其实也是开一个数组来统计，再开一个函数用来做区间乘，每次判断区间、下发懒标记、最后合并区间，其实和加的思路一样，这里沿用一句全站最强管理员 Xylophone 的五字真言。

E 题要取模！👊👊👊

别忘了取模！

typedef long long ll;
const int MAXN=100005;//线段树开4倍空间
ll tree[MAXN*4];
ll add[MAXN*4];
ll mul[MAXN*4];
ll a[MAXN];
int n, q, MOD;
void build(int p,int l,int r)
{
    mul[p]=1;
    add[p]=0;
    if(l==r)
    {
        tree[p]=a[l]%MOD;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=(tree[p*2]+tree[p*2+1])%MOD;
}
void pushdown(int p,int l,int r)
{
    int mid=(l+r)/2;
    int ls=p*2, rs=p*2+1;
    
    tree[ls]=(tree[ls]*mul[p]+add[p]*(mid-l+1))%MOD;
    mul[ls]=(mul[ls]*mul[p])%MOD;
    add[ls]=(add[ls]*mul[p]+add[p])%MOD;

    tree[rs]=(tree[rs]*mul[p]+add[p]*(r-mid))%MOD;
    mul[rs]=(mul[rs]*mul[p])%MOD;
    add[rs]=(add[rs]*mul[p]+add[p])%MOD;
    
    mul[p]=1;
    add[p]=0;
}
void update_mul(int p,int l,int r,int L,int R,ll k)
{
    if(L<=l&&r<=R)
    {
        tree[p]=(tree[p]*k)%MOD;
        add[p]=(add[p]*k)%MOD;
        mul[p]=(mul[p]*k)%MOD;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(L<=mid) update_mul(p*2,l,mid,L,R,k);
    if(R>mid) update_mul(p*2+1,mid+1,r,L,R,k);
    tree[p]=(tree[p*2]+tree[p*2+1])%MOD;
}
void update_add(int p,int l,int r,int L,int R,ll k)
{
    if(L<=l&&r<=R)
    {
        tree[p]=(tree[p]+k*(r-l+1))%MOD;
        add[p]=(add[p]+k)%MOD;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)/2;
    if(L<=mid) update_add(p*2,l,mid,L,R,k);
    if(R>mid) update_add(p*2+1,mid+1,r,L,R,k);
    tree[p]=(tree[p*2]+tree[p*2+1])%MOD;
}
ll query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tree[p]%MOD;
    pushdown(p,l,r);
    int mid=(l+r)/2;
    ll res=0;
    if(L<=mid) res=(res+query(p*2,l,mid,L,R))%MOD;
    if(R>mid) res=(res+query(p*2+1,mid+1,r,L,R))%MOD;
    return res;
}
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,1,n);//建区间1~n
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x, y;
            ll k;
            cin>>x>>y>>k;
            update_mul(1,1,n,x,y,k%MOD);
        }
        else if(op==2)
        {
            int x, y;
            ll k;
            cin>>x>>y>>k;
            update_add(1,1,n,x,y,k%MOD);
        }
        else
        {
            int x, y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)%MOD<<'\n';
        }
    }
}

P4588 [TJOI2018] 数学计算

妙妙题。

反正你们都会写 $op=1$ 的，那就来看操作 $2$ 吧。

我们先要知道线段树里放的是啥，比如说 $tr[v]$ ，它放的是第 $v$ 次操作的乘数，那操作 $1$ 就是在第 $v$ 个位置放这个乘数。

那么操作 $2$ ，就是除掉这个乘数，不就是把那个放被除掉的数的位置清空吗？/震惊/思考/炸开

由于线段树维护的是乘积，那么我们的 $tr[1]$ ，也就是管 $1-q$ 的这个乘积，就是我们的答案，所以对于 $op=2$ 的情况，先撤销 $pos$ 位置的乘数，更新完后输出 $tr[1]$ 就行。

typedef long long ll;
const int MAXN=100005;//线段树开4倍空间
ll tree[MAXN*4];
int t, q;
ll MOD;
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p]=1;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p]=(tree[p*2]*tree[p*2+1])%MOD;
}
void update(int p,int l,int r,int pos,ll val)
{
    if(l==r)
    {
        tree[p]=val%MOD;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) update(p*2,l,mid,pos,val);
    else update(p*2+1,mid+1,r,pos,val);
    tree[p]=(tree[p*2]*tree[p*2+1])%MOD;
}
int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    cin>>t;
    while(t--)
    {
        cin>>q>>MOD;
        memset(tree,0,sizeof tree);//注意下先清空线段树避免数据残存
        build(1,1,q);
        for(int i = 1;i<=q;i++)
        {
            int op;
            ll v;
            cin>>op>>v;
            if(op==1) update(1,1,q,i,v);
            else update(1,1,q,(int)v,1);//撤销，就是把值改成1，这样不会影响总值
            cout<<tree[1]<<"\n";
        }
    }
}

有帮助，赞一个

去预览

0/2000

全部评论 5

prediction
置顶
不写是因为自己没学。

2026-09-02 来自浙江
0
yxdl1
线段树是头大肥猪 \o/\o/

2026-09-02 来自浙江
2
- prediction
  回复
  yxdl1
  是不是吃了你放的蛋糕的原因，我觉得它又香又想咬
  
  2026-09-03 来自浙江
  0
- yxdl1
  回复
  prediction
  咬拆开是什么
  
  2026-09-04 来自浙江
  0
- prediction
  回复
  yxdl1
  把咬隔开是为什么/智斗
  
  2026-09-04 来自浙江
  0
Xylophone
P4588，哪里妙了

2026-09-05 来自广东
0
- prediction
  回复
  Xylophone
  区和队爷的思维方式和评判标准不同，对不起了xyl大人，不要禁言我
  
  2026-09-05 来自浙江
  0
- Xylophone
  回复
  prediction
  没事，我已经习惯别人把我看成区了
  
  2026-09-05 来自广东
  0
- prediction
  回复
  Xylophone
  PPPPP
  
  2026-09-05 来自浙江
  0
Xylophone
E 题要取模！👊👊👊

2026-09-05 来自广东
0
Asdfre
？？！强强？？！

2026-09-04 来自广东
0
- prediction
  回复
  Asdfre
  ？？！我弱弱？？！
  
  2026-09-04 来自浙江
  0

知识概括

正题

E 题 要 取 模 ！👊👊👊

全部评论 5

热门讨论

E 题要取模！👊👊👊