线段树入门

idle_onlooker · 2025-11-12 15:36:15 · 算法·理论

前言

笔者从 2025.4.22 第一次通过线段树模板，至今也不过半年时间，虽然短暂，但是却让其成为了笔者最喜欢的算法，因此，我常常会大喊我是线段树的狗。为了帮助自己记忆以及造福后人，笔者提键盘敲出了这篇文章。 ——2025.10.29

为什么要学线段树

我认为线段树是世界上最好用的数据结构，没有之一！！！
当然，我直接这么说你是肯定不信的，让我们看看线段树都能干什么。
对于一颗线段树，它能支持：在单次时间复杂度为 O(\log n) 的情况下进行区间修改，查询。

Q：没了？
A：对，没了。

那我学个蛋，跑路了。
等等先别走，那我问你，你暴力对一个数组进行区间修改的最坏时间复杂度是不是 O(n) 的？
你说是？但是线段树可以 O(\log n) 啊，这难道真的不值得你学一下吗？
你说不值得？
我*%^#^#%#
算了，闲话少说，让我们进入正题。

关于线段树的介绍

线段树长什么样？
长这样
这张图是什么意思呢？
每个方格代表一个线段树的节点。
每个节点上面的 id 代表这个点的编号。
而节点中写的 [L,R] 则代表这个节点维护下标范围在 L\sim R 的区间。
例如编号为 5 的节点维护的是下标为 4\sim 5 的区间。

由观察可以得到，对于一个节点，如果它维护的区间 [L,R] 满足 L\ne R 那么它一定会有两个儿子节点(我们将其称作左儿子和右儿子)，如果这个点的编号为 id，那么它的左儿子的编号为 id\times 2，右儿子的编号为 id\times 2+1。
它的左儿子维护的区间为 [L,\lfloor \frac{L+R}{2}\rfloor]。
它的右儿子维护的区间为 [\lfloor \frac{L+R}{2}\rfloor+1,R]。
知道这些基础概念之后我们就可以尝试实现一颗线段树了。

* 注：下文中的 L,R 均代表当前线段树节点维护的区间的左右端点，mid 均代表 \lfloor \frac{L+R}{2}\rfloor，l,r 代表查询区间（此限制对代码内的变量仍然适用）。

线段树的简单实现

我们首先要建树，现在假设我们维护长度为 n 的数组 a 的区间和。

建树

void make_tree(int L,int R,int id){
    if(L==R){//到达叶子结点，没有左右儿子
        tree[id].sum=a[L];//直接赋值
        return ;//退出建树函数
    }
    int mid=(L+R)>>1;
    make_tree(L,mid,id<<1);//递归左儿子
    make_tree(mid+1,R,id<<1|1);//递归右儿子
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;//当前节点维护的区间和使用左右儿子来得到。
}

这个代码的时间复杂度是什么？
对于每一个线段树节点，我们都会运行一次建树函数，所以线段树有多少节点，函数就会运行几次。

那线段树节点数是多少？
我们尝试不那么严谨的证明一下。
线段树其实就是一颗二叉树。
满二叉树的节点数是 2\times n-1（假设最后一层的节点数为 n）。

我们进行思考，此时最坏情况下就是将一颗满二叉树的最右下角的节点增加一个右儿子。
这个右儿子的编号为 (2\times n-1)\times 2+1=4\times n-1。
所以线段树的节点数最多是 4\times n-1 个。

当然 4n 只是一个上界。
如果卡空间的话我们可以将其开到第一个 \ge n 的 2 的整数次幂的二倍。
也非常好理解，2 的整数次幂的节点数是它的二倍，由于 n\le 这个数，所以数组长度为 n 的线段树的最大节点编号不可能大于这个数，所以开到这么大就够用。

当然如果极限卡空间你可以直接运行建树函数，开个变量记录最大的节点编号是多少就行了。

区间查询

还是刚才的图片
假设现在我们要查询区间 [2,7]。
那我们的答案就应用 id={17,9,5,12} 得出。
怎么实现？

我们先给代码，根据代码里面的注释进行理解。

int query(int l,int r,int L,int R,int id){
    if(l<=L&&r>=R) return tree[id].sum;
    //如果当前节点区间 [L,R]⊆[l,r]（完全被查询区间包含），直接返回
    int mid=(L+R)>>1,ans=0;
    if(l<=mid) ans+=query(l,r,L,mid,id<<1);
    //如果查询区间与左儿子区间 [L,mid] 满足 [l,r]∩[L,mid]≠∅（有交集），递归左儿子并累加答案 
    if(r>mid/*写成r>=mid+1也可以*/) ans+=query(l,r,mid+1,R,id<<1|1);
    //如果查询区间与右儿子区间 [mid+1,R] 满足 [l,r]∩[mid+1,R]≠∅（有交集），递归右儿子并累加答案 
    return ans;
    //返回答案 
}

现在问题来了，如何证明这个函数是 O(\log n) 的，相信大多数初学者甚至已经学会线段树较长时间的人都不能给出一个比较完整的证明。
笔者在这里给出一个自己推出的证明方式。
首先要明确的是一颗线段树的深度是 \log n 的。
深度每增加一层，维护的区间长度会除以 2。
这个很好理解。

假设查询区间为 [l,r]。
显然我们第一次调用函数一定会先访问节点编号为 1 的节点。
我们进行分类讨论：

• 情况 1：

当 l=1。

如果 r>mid 那么会同时递归左右儿子，而左儿子由于 [L,mid]⊆[l,r]（完全被包含）会直接在被访问时 return 掉，而递归右儿子时又会面对查询区间的右端点小于等于当前节点维护的右端点的情况，于是这个节点就会面对和它的父亲相同的情况。

如果 r\le mid 则只会递归左儿子，之后的情况就是 r>mid 的简易版了。

此时线段树的每层最坏会有两个节点被访问，时间复杂度 O(2\times\log n)。

• 情况 2：

当 r=n。

基本同上，不解释。

• 情况 3：

当 l\le mid\le r。

我们会递归左右儿子，此时左儿子会退化成情况 2,右儿子会退化成情况 1。

线段树的每层最坏会有四个节点被访问，时间复杂度 O(4\times\log n)。

• 情况 4：

当 [l,r]⊆[L,mid]（查询区间完全在左儿子区间内）。

递归左儿子，在多次递归后迟早会退化成情况 1 或情况 2 或情况 3。

线段树的每层最坏依旧会有四个节点被访问，时间复杂度 O(4\times\log n)。

• 情况 5：

当 [l,r]⊆[mid+1,R]（查询区间完全在右儿子区间内）。

基本同上，不解释。

证毕。

可能写的比较抽象，但是没关系，其实你只需要知道线段树是单次查询 O(\log n) 的即可（对，其实你不明白也问题不大，但是我还是写了，也是因为笔者也因这个问题困惑了一段时间）。

区间查询就先到这里，现在就要讲修改了。

单点修改

其实学会查询后修改就没什么好说的了，直接上代码。

void add(int l,int k,int L,int R,int id){
    if(L==R){//到达修改的点
        tree[id].sum+=k; 
        return ;
    }
    int mid=(L+R)>>1;
    if(l<=mid) add(l,k,L,mid,id<<1);
    //修改点 l∈[L,mid]（在左儿子区间内） 
    else add(l,k,mid+1,R,id<<1|1);
    //否则修改点 l∈[mid+1,R]（在右儿子区间内） 
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    //不要忘记用儿子更新自己 
}

这个代码的时间复杂度很好证明，线段树的每层一定会有一个节点被访问，时间复杂度 O(\log n)。

现在我们就可以 AC P3374 【模板】树状数组 1了。

但是为什么是单点修改，不是区间修改吗，退钱！！！

别急，马上就讲。

区间修改与懒标记

区间修改怎么办。
这时候有人要说了：暴力递归到每一个要修改的节点，然后像单点修改一样就行了。

没错……个蛋。
那我问你，这样和暴力循环修改有什么区别吗？
是不是最坏还是 O(n) 的。
甚至本来 O(1) 的查询还降到 O(\log n) 了。

此时需要我们引入一个新的概念，懒惰标记。
假设一下我们现在进行的操作是把区间内的每个数都增加 k。
我们尝试使用类似区间查询的函数进行修改。
然后给访问到的节点打上标记，表示当前区间需要整体增加多少。

当然，我们在访问到这个节点的时候也要把它的懒标记下放到儿子节点。
代码实现如下：

void pushdown(int id,int L,int R){
    int mid=(L+R)>>1,k=tree[id].tag;
    tree[id<<1].sum+=(mid-L+1)*k;
    tree[id<<1|1].sum+=(R-mid)*k;
    tree[id<<1].tag+=k;
    tree[id<<1|1].tag+=k;
    tree[id].tag=0;
}
void add(int L,int R,int l,int r,int k,int id){
    if(l<=L&&r>=R){
        tree[id].tag+=k;
        tree[id].sum+=(R-L+1)*k;
        //更新懒标记和此节点维护的区间和（当前节点区间 [L,R]⊆[l,r]）
        return ;
    }
    pushdown(id,L,R);
    //下放懒标记的函数
    int mid=(L+R)>>1;
    if(l<=mid) add(L,mid,l,r,k,id<<1);
    //查询区间与左儿子区间满足 [l,r]∩[L,mid]≠∅，递归左儿子
    if(r>mid) add(mid+1,R,l,r,k,id<<1|1);
    //查询区间与右儿子区间满足 [l,r]∩[mid+1,R]≠∅，递归右儿子
    tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
    //不要忘记更新 
}

还是比较简单的。

此时，我们可以轻松通过P3368 【模板】树状数组 2和P3372 【模板】线段树 1。

多种懒标记

看这道题P3373 【模板】线段树 2。
同时进行区间乘法和加法。
其实也比较简单，我们只需要维护两个懒标记即可。

但是难点在于下放懒标记的顺序，其实无非就两种下放顺序，我们直接分类讨论（分讨大法好）。

• 先加后乘

先说结论：不对。
我们考虑对同一个节点先进行乘法操作，后进行加法操作。
那么如果我们先下放加法懒标记再进行乘法很显然会出问题。

当然，有人可能会提出用加法的数除去乘法的数不就行了，我的评价是，你精度不要（其实目前有一个貌似可行的设想是用快速幂求逆元）？

• 先乘后加

我们考虑对同一个节点先进行乘法操作，后进行加法操作，显然不会出现问题。
我们考虑对同一个节点先进行加法操作，后进行乘法操作，我们在进行乘法操作时把加法的懒标记乘一下然后下放即可。

具体操作见代码。

void pushdown(int id){
    if(tree[id].mul_tag!=1){
        //乘法的初始值是1，不是0！！！！！ 
        int k=tree[id].mul_tag;
        tree[id<<1].sum*=k;
        tree[id<<1].mul_tag*=k;
        tree[id<<1].add_tag*=k;
        tree[id<<1].sum%=mod;
        tree[id<<1].mul_tag%=mod;
        tree[id<<1].add_tag%=mod;
        tree[id<<1|1].sum*=k;
        tree[id<<1|1].mul_tag*=k;
        tree[id<<1|1].add_tag*=k;
        tree[id<<1|1].sum%=mod;
        tree[id<<1|1].mul_tag%=mod;
        tree[id<<1|1].add_tag%=mod;
        tree[id].mul_tag=1;
    }
    if(tree[id].add_tag){
        int k=tree[id].add_tag;
        tree[id<<1].sum+=(tree[id<<1].r-tree[id<<1].l+1)*k;
        tree[id<<1].add_tag+=k;
        tree[id<<1].sum%=mod;
        tree[id<<1].add_tag%=mod;
        tree[id<<1|1].sum+=(tree[id<<1|1].r-tree[id<<1|1].l+1)*k;
        tree[id<<1|1].add_tag+=k;
        tree[id<<1|1].sum%=mod;
        tree[id<<1|1].add_tag%=mod;
        tree[id].add_tag=0;
    }
}
void add(int l,int r,int k,int id){
    int L=tree[id].l,R=tree[id].r;
    if(l<=L&&r>=R){
        tree[id].sum+=(R-L+1)*k;
        tree[id].add_tag+=k;
        tree[id].sum%=mod;
        tree[id].add_tag%=mod;
        return ;
    }
    pushdown(id);
    int mid=(L+R)>>1;
    if(l<=mid) add(l,r,k,id<<1);
    //[l,r]∩[L,mid]≠∅，递归左儿子
    if(r>mid) add(l,r,k,id<<1|1);
    //[l,r]∩[mid+1,R]≠∅，递归右儿子
    tree[id].sum=(tree[id<<1].sum+tree[id<<1|1].sum)%mod;
}
void mul(int l,int r,int k,int id){
    int L=tree[id].l,R=tree[id].r;
    if(l<=L&&r>=R){
        tree[id].sum*=k;
        tree[id].mul_tag*=k;
        tree[id].add_tag*=k;
        //把加法懒标记也乘k 
        tree[id].sum%=mod;
        tree[id].add_tag%=mod;
        tree[id].mul_tag%=mod;
        return ;
    }
    pushdown(id);
    int mid=(L+R)>>1;
    if(l<=mid) mul(l,r,k,id<<1);
    //[l,r]∩[L,mid]≠∅，递归左儿子
    if(r>mid) mul(l,r,k,id<<1|1);
    //[l,r]∩[mid+1,R]≠∅，递归右儿子
    tree[id].sum=(tree[id<<1].sum+tree[id<<1|1].sum)%mod;
}

不要忘记取模！不要忘记取模！不要忘记取模！
之后就轻松 AC 了。

线段树的简单变种

线段树拥有许多扩展，在比赛中，它们甚至比线段树本身更常用，所以学习线段树的变种也是非常重要的。

树状数组

虽然线段树能够实现树状数组的所有操作，但是树状数组依旧凭借着极小的常数（严格 O(\log n)），更优的空间（严格 O(n)）和简单的代码在数据结构中占有一席之地。

树状数组的一些基本概念及简单实现

• 1. lowbit