本文章暂不包含可持久化线段树、动态开点相关内容，仅逐步介绍基本的线段树。

线段树是一种常用的特殊树数据结构，在 NOI 大纲 中难度被标为【6】级，提高级。

线段树通过维护一颗树来快速存储调用线性数组的值。

下面循序渐进地介绍线段树。

基本架构

令线段树要维护的内容为数组 a 的任意区间的函数 f(l,r)，并且有 f(l,r)=g(f(l,mid),f(mid+1,r))(mid\in[l,r))（表示合并），f(l,l) 可以 O(1) 计算。

线段树的根结点维护了整个数组 a，区间 [1,n] 的值。

我们现在还不能直接得到根结点的值，所以我们给它设两个儿子，为了让两个儿子“均匀” 一点，左右儿子是由根结点对半分开得到的（分治思想）。具体地说，对于区间 [l,r]，令 mid=(l+r)/2，左二子维护 [l,mid]，右儿子维护 (mid,r]。

一直这样分下去，直到发现一个结点维护的值是 [l,l] 时，这个结点就没有儿子了，它的值本身可以直接求出来。

对于有儿子的结点，它的值可以用 g（先前定义的）计算左右儿子的值，从而得到它自己的值。

所以无论一个结点有没有儿子，它维护的值都是可以求出来的。我们成功地定义了一颗线段树。

维护内容

线段树维护数据的修改和询问都需要满足结合律。

比如说询问数组 a 的区间最大值，如果询问 [l,r]，我们发现

\forall i\in[l,r),\max_{j=l}^{r}a_j=\max(\max_{j=l}^ia_j,\max_{j=i+1}^ra_j)

这个性质，也就是说 [l,r] 的最大值就是 [l,i] 的最大值和 (i,r] 的最大值中的较大值，这个 i 可以任意选取，说明取较大值这个操作满足结合律；

另一个例子：询问区间和，

\forall i\in[l,r),\sum_{j=1}^{r}a_j=\sum_{j=l}^{i}a_j+\sum_{j=i+1}^{r}a_j

这也是显而易见的，前半段的和加上后半段的和不就是整一段的和么？所以说加法满足结合律。

类似地，乘法（求积）、求最小值、求最大子段和也满足结合律。不一定要满足交换律，例如矩阵积（矩阵乘法）。

结合律不一定能够轻易判断，例如最大子段和。其维护方法为：\ 令 \text{lef}(l,r) 表示 [l,r] 内以 l 为最左端的最大子段和，\text{rig}(l,r) 表示 [l,r] 内以 r 为最右端的最大子段和，\text{sum}(l,r) 表示 [l,r] 所有数的总和，\text{ans}(l,r) 表示 [l,r] 的最大子段和，\forall mid\in[l,r)，有维护过程：

\text{lef}(l,r)=\max(\text{lef}(l,mid),\text{sum}(l,mid)+\text{lef}(mid+1,r))\\ \text{rig}(l,r)=\max(\text{rig}(mid+1,r),\text{sum}(mid+1,r)+\text{rig}(l,mid))\\ \text{sum}(l,r)=\text{lef}(l,mid)+\text{sum}(mid+1,r)\\ \text{ans}(l,r)=\max(\text{ans}(l,mid),\text{ans}(mid+1,r),\text{rig}(l,mid)+\text{lef}(mid+1,r))

虽然用了很多数据辅助维护，但它们仍然满足结合律，所以也可以用线段树去维护。

基本架构

线段树是一种特殊树，下图为存储了一个大小为 14 的数组相关信息的线段树。发现若线段树维护区间大小为 n，则线段树有 2n-1 个结点。但如果使用 2i 和 2i-1 分别表示 i 的左右儿子，由于最后一层在边界条件下可能会多出若干结点，所以线段树下标可能达到 4n 级别。由于此表示方法比较简便，本文后续内容中代码采用此方法。

由上图可以发现线段树叶子结点的深度不是相同的，但是一个结点要么是叶子结点，要么具有两个儿子。建树时以此进行分类递归。

建树

如果线段树结点初始值不为 0，我们就需要建树。如上文所述，一个非叶子结点的值不能直接求出，依赖于它的两个儿子。所以递归程序中，我们先递归更新 / 求出一个结点儿子的值，再更新其本身的值。

对于建树，我们需要根据线段树维护的数据具体类型预写出两个函数，分别用来将原先数组中的初始值转化为其对应的叶子结点的值，和用一个结点的左右儿子的值得出此结点的值。

参考建树模板：

void build(int k,int l,int r){//当前递归结点 k，对应原数组区间 [l,r] 
    if(l == r){//叶子结点，直接从原数组中转 
        st[k] = change(a[l]);
        return;
    }
    int mid = l + r >> 1;//不是叶子结点，此为左右儿子区间分界点 
    build(k << 1,l,mid);//递归左儿子 
    build(k << 1 | 1,mid + 1,r);//递归右儿子
    pushup(k);//获得该结点的值
    return; //位运算加速，2x = x<<1，2x+1 = x<<1|1
}

代码中两个函数的具体内容以维护区间和为例：

int change(int x){//将原数组中的 x 转换成它的区间和 
    return x;//x 构成的区间，区间和显然等于 x 
}
void pushup(int x){//由 x 的儿子更新 x 
    st[x] = st[x << 1] + st[x << 1 | 1];//x 代表的区间左半边区间和为左儿子的值 sum_{2x}，右半边区间和为 sum_{2x+1} 
    return;//位运算加速，2x = x<<1，2x+1 = x<<1|1 
}

实际上我们习惯把 change 直接写在 build 函数中。

时间复杂度：每个点更新一次，复杂度 O(n)。

线段树实现 - 单点修改 & 区间查询

单点修改

注意：由于洛谷上线段树题目起步过难，以下讲解题目中需要使用 CodeForces 中的课程题目，请先登录 CodeForces 并报名其中的免费的数据结构课程，便于后续做题。

如果从原数组的角度去考虑单点修改，直接受到影响的是其对应的叶子结点。\ 然而只修改一个叶子结点肯定是不对的，毕竟

一个非叶子结点的值不能直接求出，依赖于它的两个儿子。

所以实际上这个叶子结点的父亲同样受到了它的影响，需要更新（可以直接调用建树时用的 pushup 函数），同理父亲的父亲、父亲的父亲的父亲… 直至根节点都需要修改。\ 然而这个操作量并不会很大，因为线段树深度约为 O(\log_2n)，所以根节点最多也只会是叶子结点的约 O(\log_2n) 辈父亲，所以单点递归修改复杂度为 O(\log n)。

具体实现：我们的递归函数需要满足以下功能：

• 从线段树根节点逐层递归至目标处；
• 从下到上更新每个从目标处返回根节点的路径上的点。

以下为单点赋值操作的参考代码。

void update_point(int aim,int num){//赋值操作对应的单点更新 
    st[aim] = num; 
} 
void upd(int k,int l,int r,int aim,int num){//当前递归结点 k，对应原数组区间 [l,r]，要将 a[aim] 修改为 num
    if(aim < l || aim > r){//目标不在当前区间内，当前位置不需要更新 
        return;
    }
    if(l == r){ 
        update_point(k,num);//找到了叶子结点，更新 
        return;
    }
    int mid = l + r >> 1;
    upd(k << 1,l,mid,aim,num);//目标可能在左儿子下，也可能在右儿子下，不妨两个都检查一遍，必然其中有一个会直接返回 
    upd(k << 1 | 1,mid + 1,r,aim,num);
    pushup(k);//牢记：无论如何，儿子更新完，父亲一定也要更新
    return; 
}

update_point 函数习惯并入 upd 函数中。

区间查询

由于线段树保存了一个区间需要查询的值，我们可以把询问区间分成若干个由不同结点保存的值，然后合并得到结果。

举例：以下是在一个线段树上查询 [4,13] 的值时，被计算的结点。\ 在这个例子中我们有四个结点要按顺序合并，这是否意味着我们需要保存这四个结点的值，在询问结束后合并呢？\ 其实不然，可以考虑这样一种操作：遇到越界的结点询问（如 [3,3]）时，不要直接退出，而是让这个节点返回一个无作用的值（如查询区间和时的 0，查询最小值时的 \infty），这样每次递归返回时我们就进行一次合并，直到返回至根时就合并出了需要的答案，而无需单独开数组。

时间复杂度 O(\log n)，因为区间连续，每一层的非叶子结点至多用上两个，其余都被父亲结点直接“包办” 了。

参考代码（区间和）：

int merge(int x,int y){//两个区间和合并为一个区间和 
    return x + y;
}
int qry(int k,int l,int r,int x,int y){//询问 [x,y] 的区间和 
    if(y < l || x > r){//当前结点与询问区间无交集，显然无用，返回一个无关紧要的值 
        return 0;
    }
    if(x <= l && y >= r){//当前结点为询问区间的子集，整个区间和都需要，就没必要调用儿子了，直接返回 
        return st[k];
    }
    int mid = l + r >> 1;
    return merge(qry(k << 1,l,mid,x,y),qry(k << 1 | 1,mid + 1,r,x,y));
}//单点修改的区间操作中结点没有变化，所以直接返回两个儿子中有用值合并的结果就可以了 

merge 函数可以直接并入区间询问函数中。

至此，单点修改、区间查询的线段树已经被成功构建。以下为 CodeForces 课程中的例题，附参考代码于文末。

例题

单点赋值与区间求和 A\ 单点赋值与区间求最小值和最小值出现的次数 B\ 单点修改求全局最大子段和 C\ 01 数字序列单点取反求全局第若干个 1 D\ 求逆序对 E\ 矩阵乘法维护 F

线段树实现 - 区间修改 & 单点查询

实际上和单点修改 & 区间查询有很多共通之处，原先的区间询问将目标通过递归拆开，统计结点上的信息；单点修改则把根到路径上的所有点都更新。\ 这一版本的线段树正好相反，区间修改将目标区间通过递归拆开，更新全部拆开来之后结点的信息；单点查询则统计从根到路径上经过的所有点都更新。

参考代码：

void upd(int k,int l,int r,int x,int y,int num){
    if(y < l || x > r){
        return;
    }
    if(x <= l && y >= r){
        add[k] += num;//由于只需要单点查询，这里线段树不再维护区间信息，而是每个区间内结点共同的信息，如同时加上某值 
        return;
    }
    int mid = l + r >> 1;
    upd(k << 1,l,mid,x,y,num);
    upd(k << 1 | 1,mid + 1,r,x,y,num);
}
int ask(int k,int l,int r,int aim){
    if(aim < l || aim > r){
        return 0;
    }
    if(l == r){
        return add[k];//结点上维护的信息 
    }
    int mid = l + r >> 1;
    return add[k] + ask(k << 1,l,mid,aim) + ask(k << 1 | 1,mid + 1,r,aim);
}

例题

区间加与单点查值 G

线段树实现 - 区间修改 & 区间查询

原型线段树中最高级的线段树。发现这次既要区间修改、又要区间询问，我们先前处理区间修改（单点询问）和区间询问（单点修改）的方式是把目标区间拆开，这次能不能同样这么做呢？

发现似乎是可以的，但是出现了一些困难，如下图所示：\ \ 修改 [4,7]，询问 [6,12] 时，实际修改的结点为所有蓝线两端的结点（即蓝框结点到根节点路径上的所有结点）；\ 之后询问 [6,12]，取了红框结点的两个数据，但是 [6,6] 应该被修改而没有被修改，出现了错误，可见直接改行不通。

我们想：要是能在递归调用 [6,6] 的时候，识别到 [4,6] 已经被修改，这样的话我们就可以知道 [6,6] 也应该被修改，这个时候补充一次修改就可以避免错误了。—— 然而，这个操作已经被大众所熟知 —— 打标记。

具体而言，如果说这个结点被操作了，它的所有后代作为子区间肯定也是要操作的，但是会超时；我们不妨在这个点上打上标记，表示以它为根的线段子树都应该被操作，但是实际上只有它自己被操作了，后续有需要再沿着查询的路径把这个标记和操作一起向下“分发”。\ 具体而言，在上面的例子中，[4,6] 和 [7,7] 被标记，递归查找 [6,12] 到达 [4,6] 这个结点时发现了先前的标记，对 [4,5] 和 [6,6] 进行标记对应的操作并标记它们，这是再往下查找就可以获得正确的 [6,6] 的值了。

参考代码（以区间加区间求和为例）：

struct node{//线段树需要维护的结点内容，因为可能有多个所以需要开结构体，简单题不卡常数的话不开也行 
    int sum,add;
};
node c[maxn << 2];//4 倍大小 
void pushup(int k){//子结点 -> 父结点 （k） 
    c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
    return;
}
void pushdown(int k,int l,int r){//父结点（k,[l,r]） 下传标记到儿子 
    c[k << 1].add += c[k].add;
    c[k << 1 | 1].add += c[k].add;//标记下传，区间加和求和一般采用每个点加上的值作为标记 
    int mid = l + r >> 1;
    c[k << 1].sum += (mid - l + 1) * c[k].add;//区间长度乘以单点加值，自然就是整段加值了 
    c[k << 1 | 1].sum += (r - mid) * c[k].add;
    return;
}
void build(int k,int l,int r){
    if(l == r){
        c[k].sum = a[l];
        return;
    } 
    int mid = l + r >> 1;
    build(k << 1,l,mid);
    build(k << 1 | 1,mid + 1,r);
    pushup(k);
    return;
}
void upd(int k,int l,int r,int x,int y,int num){
    if(y < l || x > r){//没有交集 
        return;
    }
    if(x <= l && y >= r){//当前点被包含，整段都要加，打标记 
        c[k].sum += (r - l + 1) * num;
        c[k].add += num;//标记
        return; 
    }
    int mid = l + r >> 1;
    pushdown(k,l,r);//坑点：这里要下传，因为待会这个结点的值需要由两个儿子的值改变，如果保持儿子没有继承标记的状态那么它们的值是不正确的，这个结点也会变得不正确 
    upd(k << 1,l,mid,x,y,num);
    upd(k << 1 | 1,mid + 1,r,x,y,num);
    pushup(k);//坑点：时刻记住儿子结点改变之后父亲结点一定要跟着改变 
    return;
}
node qry(int k,int l,int r,int x,int y){
    if(y < l || x > r){
        return {0,0}; 
    }
    if(x <= l && y >= r){
        return {c[k].sum,0};//标记返回没有用
    }
    int mid = l + r >> 1;
    pushdown(k,l,r);//坑点：牢记任何时候只要用到儿子结点的值，包括询问和更新父亲，这个时候都要下传 
    node lef = qry(k << 1,l,mid,x,y);
    node rig = qry(k << 1 | 1,mid + 1,r,x,y);
    return {lef.sum + rig.sum,0}; 
} 

以上就是全部模板，基本上修改 pushdown 和 pushup 函数之后就可以直接套用，但为了锻炼码力还是建议做每道题的时候都单独敲一遍。

一些毒瘤题可能需要同时满足多种操作，所以有时一个结点需要维护两种 tag，这种情况请读者自行探索，注意标记的优先级以及两个重点问题：

• 当一个线段树上的结点的祖先存在标记时，这个结点的值和标记值是错误的（未更新），绝对不能调用；
• 一个线段树上的结点的儿子被更新（不包括标记下传）时，这个结点一定要被更新。

例题

加与最小值 H\ 乘与和（取模）I\ 赋值与最大子段和 J\ 加与区间元素后继 K\ 赋值、加与和 L\ 加等差数列与单点值 M

例题参考代码及提示

云剪贴板

后续建议

线段树作为提高级接触到的最早的递归数据结构应用，存在相对高难度的代码能力和逻辑分析能力。

如果读者希望在线段树方面学习更多内容（动态开点等），可以进一步结构体封装线段树，对复杂的写法大有裨益；如果只需要这种最基础的线段树，那么花一周以内的时间做完 CF 和洛谷上经典的一些的题就足矣，线段树是一种实现细节较多的算法，不勤加练习是很难得心应手的。

闲话

第一次做这么长的教程，感觉还有很多仍需完善的地方，欢迎各位提出宝贵意见！