本篇只讲基础线段树。以下内容以求区间和线段树为例。

---

前置知识：

二分、分治思想，堆式建树。

对于节点 $i$，他的左孩子节点索引为 $2\times i$，右孩子索引为 $2\times i+1$。这样我们可以将线段树储存在数组中。我们先准备两个取儿子函数，其中 now 为当前节点，后面要用。

int left_child(int now){//取左孩子，返回的是索引
    return 2*now;
}
int right_child(int now){//取右孩子
    return 2*now+1;
}
        

---

什么是线段树？

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 $\mathcal{O}(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
—— $OI$ $Wiki$

线段树将一个区间按照递归顺序逐步往下分解，每个长度大于 $1$ 的区间被分解为两个小区间，这些小区间会被继续分解知道不能再分为止。线段树可以用于维护具有结合律特性的区间查询操作。例如加法，乘法，最值。

举个例子，比如说对于序列 $\{1,2,3,4,5,6\}$，设定其左右区间分别为 $1,6$。那么可以绘制出线段树如下图所示：

为了方便理解我们转换成树形结构。

可见线段树通常被视为一颗完全二叉树（更准确地说是平衡二叉树）。这颗二叉树的每一个叶子节点都代表着这个序列其中一个元素的值。（因为左区间与右区间相等）

那么接下来，我们开始学习线段树的相关操作。

---

建树

根据线段树的特性（即将每一个长度不为一的区间划分成左右两个区间），我们可以将一个区间对半分，然后递归对半分后的两个区间，再给它对半分，一直到区间长度为 $1$ 为止，然后再回溯求区间和。下面我们用一个具体例子来描述这一过程。

首先我们有一个长度为 $6$ 的序列，为 $\{1,20,2,6,5,4\}$。我们先构建出这棵线段树。

将区间 $[1,6]$ 对半分，分为 $[1,3],[4,6]$ 两个区间。

接下来来我们按照递归顺序递归左孩子，将区间 $[1,3]$ 对半分，分为 $[1,2],[3,3]$ 两个区间。

按照顺序，我们把区间 $[1,2]$ 对半分，分为 $[1,1],[2,2]$ 两个区间

此时我们发现两个区间的长度都为 $1$ 了，那么我们就把这两个叶子节点赋值，分别为赋值为 $1,20$。回溯至区间 $[1,2]$，赋值为它的两个孩子值的和，即为 $1+20=21$。此时回溯到区间 $[1,3]$，递归右孩子 $[3,3]$，发现区间长度为 $1$，赋值为 $2$。回溯到区间 $[1,3]$，赋值为两个孩子之和，即为 $21+2=23$。

接下来我们回溯到区间 $[1,6]$，递归右孩子 $[4,6]$。对半分分为区间 $[4,5],[6,6]$

后面我就不细讲了，最终的线段树如下图所示。

那么我们就可以写出线段树的建树函数。

void build(int now,int l,int r){//递归建树
    tree[now].lazy=0;//懒标记的初始化，后面会讲
    if(l==r){//叶子节点
        tree[now].data=a[l];
        return ;
    }int mid=l+(r-l)/2;
    build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
    tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
}

时间复杂度分析：

线段树可以被看作一棵完全二叉树，若序列长度为 $n$，那么线段树的节点数为 $2n-1$，故复杂度为 $\mathcal{O}(n)$

---

区间查询

现在我们构建好了一棵线段树，那么我们该如何进行区间查询操作呢？

我们按照上述构建好的线段树为例，来查询区间 $[2,4]$ 的和。

首先我们看区间 $[1,6]$

我们发现所求区间与区间 $[1,6]$ 并不匹配^[1]，所以我们向下进行寻找。我们来到区间 $[1,6]$ 的两个孩子。

这时候我们发现这两个区间与所求区间仍然不匹配，我们就继续向下寻找

此时我们发现只有区间 $[3,3]$ 与所求区间匹配，我们就将结果加上区间 $[3,3]$ 的值 $2$。对于区间 $[6,6]$，我们发现他不匹配所求区间，我们直接返回 $0$ 即可^[2]。对于其他区间，我们继续向下递归。

同样的，筛去不匹配的区间，我们最终剩下了：

最后区间 $[2,4]$ 的结果就是这三个区间的值相加。结果为 $21+2+6=29$。

由此我们可以写出线段树区间查询函数的代码，如下所示

int query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
    if(ql>r or qr<l)return 0;//如果不匹配返回 0
    if(ql<=l and qr>=r)return tree[now].data;//否则返回当前区间的值
    int mid=l+(r-l)/2;
    pushdown(now,l,r);//懒标记的处理，后序会讲
    return query_add(left_child(now),l,mid,ql,qr)+query_add(right_child(now),mid+1,r,ql,qr);//递归左右两个孩子，同时返回这两个值的和。
}

时间复杂度分析

线段树最多有 $2n+1$ 个节点，每次递归左右两边的区间，平均一下复杂度为 $O(\log n)$

---

区间更新

如果根据查询函数直接写更新函数，需要下降更新这个区间中的每一个元素，复杂度高达 $n \log n$，这个时候我们引入一个新的概念用以优化，懒标记。

懒标记 lazy tag 优化

懒标记，顾名思义就是偷懒的（

我们发现只有当操作时经过这一区间时才需要获取他的值，我们大可以等到需要用到这个区间的值时在进行更新。

我们将储存线段树的数组加上一个值 $lazy$ 用于储存这个节点的懒标记。只有当需要这个节点的值时，我们再将懒标记下发，并清空当前节点的懒标记。对于区间和问题，若需将区间 $[l,r]$ 加上 $k$，下发懒标记时需要加上 $(r-l+1)\times k$。在懒标记优化后，每次搜索的时间可以优化为 $O(\log n)$。

据此，我们可以写出一个 pushdown 函数用来下传懒标记。如果当前节点懒标记不为 $0$ 我们就下发他，否则不做任何操作，注意在下发完后把当前节点的懒标记设为 $0$。

void pushdown(int now,int l,int r){//懒标记的处理
   if(tree[now].lazy!=0){
      int mid=(l+r)/2;
       tree[left_child(now)].data+=tree[now].lazy*(mid-l+1);
       tree[left_child(now)].lazy+=tree[now].lazy;
       tree[right_child(now)].data+=tree[now].lazy*(r-mid);
       tree[right_child(now)].lazy+=tree[now].lazy;
       tree[now].lazy=0;
   }
}

在学习完懒标记优化后，我们来看区间更新代码实现过程。

1. 当区间完全不匹配时，我们直接返回。
2. 如果当前区间匹配，我们直接更新当前区间的值，并返回
3. 下发当前节点的懒标记
4. 更新左区间
5. 更新右区间
6. 将当前节点值更新为他的两个孩子的值之和。

代码易得

void update_range(int now,int l,int r,int ul,int ur,int val){//区间更新
    if(ul>r or ur<l)return ;
    if(ul<=l and ur>=r){
        tree[now].data+=1LL*val*(r-l+1);
        tree[now].lazy+=val;
        return ;
    }int mid=l+(r-l)/2;
    pushdown(now,l,r);
    update_range(left_child(now),l,mid,ul,ur,val);
    update_range(right_child(now),mid+1,r,ul,ur,val);
    tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}

单点更新

这里不细讲，具体实现和区间更新函数类似。如果不想写可以在调用区间更新函数时将左右区间设为你想更新的那个点。具体代码如下。

void update(int now,int l,int r,int idx,int val){//单点更新
    if(l==r){
        tree[now].data=val;
        return ;
    }int mid=l+(r-l)/2;
    pushdown(now,l,r); 
    if(idx<=mid){
        update(left_child(now),l,mid,idx,val);
    }else{
        update(right_child(now),mid+1,r,idx,val);
    }tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}

完整代码

将上述函数封装，可得如下代码：

class segment_tree{
    private:
        struct node{
            int lazy=0,data;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }void pushdown(int now,int l,int r){//懒标记的处理
            if(tree[now].lazy!=0){
                int mid=(l+r)/2;
                tree[left_child(now)].data+=tree[now].lazy*(mid-l+1);
                tree[left_child(now)].lazy+=tree[now].lazy;
                tree[right_child(now)].data+=tree[now].lazy*(r-mid);
                tree[right_child(now)].lazy+=tree[now].lazy;
                tree[now].lazy=0;
            }
        }
    public:
        void build(int now,int l,int r){//递归建树
            tree[now].lazy=0;//懒标记的初始化，后面会讲
            if(l==r){//叶子节点
                tree[now].data=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
        }
        long long query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql>r or qr<l)return 0;
            if(ql<=l and qr>=r)return tree[now].data;
            int mid=l+(r-l)/2;
            pushdown(now,l,r);
            return query_add(left_child(now),l,mid,ql,qr)+query_add(right_child(now),mid+1,r,ql,qr);
        }
        void update(int now,int l,int r,int idx,int val){//单点更新
            if(l==r){
                tree[now].data=val;
                return ;
            }int mid=l+(r-l)/2;
            pushdown(now,l,r); 
            if(idx<=mid){
                update(left_child(now),l,mid,idx,val);
            }else{
                update(right_child(now),mid+1,r,idx,val);
            }tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
        }
        void update_range(int now,int l,int r,int ul,int ur,int val){//区间更新
            if(ul>r or ur<l)return ;
            if(ul<=l and ur>=r){
                tree[now].data+=1LL*val*(r-l+1);
                tree[now].lazy+=val;
                return ;
            }int mid=l+(r-l)/2;
            pushdown(now,l,r);
            update_range(left_child(now),l,mid,ul,ur,val);
            update_range(right_child(now),mid+1,r,ul,ur,val);
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
        }
};

当然，线段树的模板需要根据实际情况进行填改或删改。

例题1：P3372

这是线段树的基础模板，将上述代码原模原样打上去即可。

例题2：P4513

（贴主也是半独立做的

题意：

现在有两种操作

1. 输出区间 $[a,b]$ 的最大子段和
2. 将第 $p$ 个值更改为 $s$

思路：

本题需要我们在维护区间和线段树的情况下输出每一次查询的最大子段和。我们发现，某区间的最大子段和有如下三种情况：

1. 全部位于该区间的左孩子
2. 全部位于右孩子
3. 两边都有

所以我么可以额外开三个变量，分别维护从左边开始的最大子段和，从右边开始的最大子段和，整个区间的最大子段和。这里分别用 l,r,maxx 表示。把懒标记扔进垃圾桶，并在先前代码基础上那个修改可以得到如下代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000005;
vector<int> a(N);
class segment_tree{
    private:
        struct node{
            int data,l,r,maxx;
        }tree[N];
        int left_child(int now){//取左孩子，返回的是索引
            return 2*now;
        }int right_child(int now){//取右孩子
            return 2*now+1;
        }void pushup(int now){//这里方便一点写了一个 pushup
            tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
            tree[now].maxx=max(tree[left_child(now)].maxx,max(tree[left_child(now)].r+tree[right_child(now)].l,tree[right_child(now)].maxx));
            tree[now].l=max(tree[left_child(now)].l,tree[left_child(now)].data+tree[right_child(now)].l);
            tree[now].r=max(tree[right_child(now)].r,tree[right_child(now)].data+tree[left_child(now)].r);
        }
    public:
        void build(int now,int l,int r){//递归建树
            if(l==r){//叶子节点
                tree[now].data=tree[now].l=tree[now].r=tree[now].maxx=a[l];
                return ;
            }int mid=l+(r-l)/2;
            build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
            pushup(now);
        }
        node query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
            if(ql<=l and qr>=r)return tree[now];
            int mid=l+(r-l)/2;
            node ml,mr,ans;
            if(qr<=mid)return query_add(left_child(now),l,mid,ql,qr);
            if(ql>mid)return query_add(right_child(now),mid+1,r,ql,qr);
            ml=query_add(left_child(now),l,mid,ql,qr);
            mr=query_add(right_child(now),mid+1,r,ql,qr);
            ans.data=ml.data+mr.data;
            ans.maxx=max(ml.maxx,max(mr.maxx,ml.r+mr.l));
            ans.l=max(ml.l,ml.data+mr.l);
            ans.r=max(mr.r,mr.data+ml.r);
            return ans;
        }
        void update(int now,int l,int r,int idx,int val){//单点更新
            if(l==r){
                tree[now]={val,val,val,val};
                return ;
            }int mid=l+(r-l)/2;
            if(mid>=idx){
                update(left_child(now),l,mid,idx,val);
            }else{
                update(right_child(now),mid+1,r,idx,val);
            }pushup(now);
        }
};
signed main(){
    segment_tree tree;
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }tree.build(1,1,n);
    while(m--){
        int op,x,y;
        cin >> op;
        cin >> x >> y; 
        
        if(op==1){
            if(x>y)swap(x,y);
            cout << tree.query_add(1,1,n,x,y).maxx << endl;
        }
        else tree.update(1,1,n,x,y);
    }
    return 0;
}

---

拓展——动态开点线段树

由于是拓展，这里讲的简略一点。

我们发现普通的线段树并不是所有节点都用到的，只有当经过该节点时才需要获取当前节点的值。所以我们可以等到需要这个节点在开。

因为这种实现方法，我们不能用堆式建树的方式来取左右孩子，我们会使用类似链表的方式，摒弃指针。在线段树结构体中储存当前节点的左右孩子，也就是在线段树结构体中再开两个成员变量 $l,r$。

区间更新

与普通线段树类似，只不过我们需要判断当前节点是否存在，不存在开一个点即可。代码易得：

void update(int &now,int l,int r,int ul,int ur,int val){
    if(!now)now=++idx;
    if(ul<=l and ur>=r){
        tree[now].data+=1LL*val*(r-l+1);
        tree[now].lazy+=val;
        return ;
    }int mid=l+(r-l)/2;
    pushdowm(now,l,r);
    if(ul<=mid)update(tree[now].l,l,mid,ul,ur,val);
    if(ur>mid)update(tree[now].r,mid+1,r,ul,ur,val);
    tree[now].data=(tree[now].l?tree[tree[now].l].data:0)+(tree[now].r?tree[tree[now].r].data:0);
}

区间查询：

一样的，判断该点是否存在即可。代码：

long long query_add(int now,int l,int r,int ql,int qr){
    if(!now)return 0;
    if(ql<=l and qr>=r)return tree[now].data;
    int mid=l+(r-l)/2;
    pushdowm(now,l,r);
    int res=0;
    if(ql<=mid)res+=query_add(tree[now].l,l,mid,ql,qr);
    if(qr>mid)res+=query_add(tree[now].r,mid+1,r,ql,qr);
    return res;
}

懒标记的下发

差不多，只不过需要提前开好左右孩子节点即可，代码：

long long query_add(int now,int l,int r,int ql,int qr){
    if(!now)return 0;
    if(ql<=l and qr>=r)return tree[now].data;
    int mid=l+(r-l)/2;
    pushdowm(now,l,r);
    int res=0;
    if(ql<=mid)res+=query_add(tree[now].l,l,mid,ql,qr);
    if(qr>mid)res+=query_add(tree[now].r,mid+1,r,ql,qr);
    return res;
}

例题：P13825

诶这不就是普通线段树模版吗，和模版 $1$ 一模一样看我复制直接提交

诶我去怎么只有 $50pts$，不是这个 $n$ 的上界怎么有 $10^9$ 啊，吓哭了

这个时候我们把动态开点直接用上即可。由于原数列是等差数列，我们可以用等差数列公式进行求解，不需要建树代码。代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=5e6+10;
int root;
struct node{
    int lazy=0,data,l,r;
};
vector<node> tree(N);
int idx;
void pushdowm(int now,int l,int r){
    if(tree[now].lazy!=0){
        if(!tree[now].l)tree[now].l=++idx;
        if(!tree[now].r)tree[now].r=++idx;
        int mid=(l+r)/2;
        tree[tree[now].l].data+=tree[now].lazy*(mid-l+1);
        tree[tree[now].l].lazy+=tree[now].lazy;
        tree[tree[now].r].data+=tree[now].lazy*(r-mid);
        tree[tree[now].r].lazy+=tree[now].lazy;
        tree[now].lazy=0;
    }
}
long long query_add(int now,int l,int r,int ql,int qr){
    if(!now)return 0;
    if(ql<=l and qr>=r)return tree[now].data;
    int mid=l+(r-l)/2;
    pushdowm(now,l,r);
    int res=0;
    if(ql<=mid)res+=query_add(tree[now].l,l,mid,ql,qr);
    if(qr>mid)res+=query_add(tree[now].r,mid+1,r,ql,qr);
    return res;
}
void update(int &now,int l,int r,int ul,int ur,int val){
    if(!now)now=++idx;
    if(ul<=l and ur>=r){
        tree[now].data+=1LL*val*(r-l+1);
        tree[now].lazy+=val;
        return ;
    }int mid=l+(r-l)/2;
    pushdowm(now,l,r);
    if(ul<=mid)update(tree[now].l,l,mid,ul,ur,val);
    if(ur>mid)update(tree[now].r,mid+1,r,ul,ur,val);
    tree[now].data=(tree[now].l?tree[tree[now].l].data:0)+(tree[now].r?tree[tree[now].r].data:0);
}
signed main(){
    int n,m;
    cin >> n >> m;
    while(m--){
        int op;
        cin >> op;
        if(op==1){
            int x,y,k;
            cin >> x >> y >> k;
            update(root,1,n,x,y,k);
        }else{
            int x,y;
            cin >> x >> y;
            int ans1=query_add(1,1,n,x,y);
            int ans2=(x+y)*(y-x+1)/2;
            cout << ans1+ans2 << endl;
        }
    }
    return 0;
}

完结撒花

---

1. 这里我们定义当前区间为 $[l_1,r_1]$，所求区间为 $[l_2,r_2]$，我们说当前区间与所求区间相匹配当且仅当 $l_2 \leq l_1 \leq r_1 \leq r_2$ ↩︎

2. 我们需要根据实际需求进行返回，这里返回 $0$ 的原因是因为一个数加上 $0$ 仍得原数。如果我们要求区间最大值，可以返回 INT_MIN。 ↩︎