图解线段树
约 2302 字大约 8 分钟
2026-01-16
引言
注意
本文如果不说明,那么所有数组都是 0--base。
「线段树是算法竞赛中常用的用来维护区间信息的数据结构。」
面对算法竞赛中的题目,如果看到区间修改与区间查询这几个字眼,那使用线段树是一个很不错的选择,它用分治(Divide and Conquer)的思想,用二叉搜索的方式将修改与查询的复杂度降低到 O(logn)。
如要继续,建议先学会:二叉树存储,前缀和,如果你学会了树状数组那更好。
信息存储
对于多个信息同时存储,使用结构体或 class 是最好的选择;为了封装度,我们选择更好用的 class。
class SegTree;
class SegTreeNode
{
public:
SegTreeNode() = default;
SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}
private:
int id;
int l, r;
SegTreeNode *parent;
int self_sum_val = 0; // 区间信息,这里指的是 sum
SegTreeNode *left;
SegTreeNode *right;
friend class SegTree;
};线段树的构建
要知道如何构建线段树,得先知道线段树长啥样,准确来说,线段树是一个二叉树,且为满二叉树 。

每一个节点代表一个区间,其中树的末端的区间长度为 1,两个子节点的父节点维护这两个子节点的信息,例如可以是和,也可以是最大值,甚至可以是 xor,这里面我们使用一个数组来举例,令 a[7]={1,3,5,3,7,2,8},那么顶端维护的数组信息 tree[0] 为所有长度的 a 数组;在其子节点分裂成两份,若为偶数,则平分长度,否则左侧比右侧长度多1,那么下面这个图描述存储信息:

这样我们可以通过递归的方式从底向上到每个节点传递信息,这样就可以填充所有 tree 数组表,参考代码如下:
class SegTree
{
public:
SegTree(const vector<int> &v)
{
n = v.size();
arr = v;
nodes.resize(4 * n, nullptr); // 线段树预先分配 4 个原数组大小 n 的空间
root = build(0, n - 1, nullptr, 0);
}
private:
int n;
SegTreeNode *root;
vector<int> arr;
vector<SegTreeNode *> nodes;
SegTreeNode *build(int arrl, int arrr, SegTreeNode *parent, int cur_cnt)
{
SegTreeNode *node = new SegTreeNode(cur_cnt);
node->parent = parent;
node->l = arrl;
node->r = arrr;
if (arrl == arrr) // 叶子节点
{
node->self_sum_val = arr[arrl];
node->left = node->right = nullptr;
nodes[cur_cnt] = node;
return node;
}
int mid = (arrl + arrr) / 2;
node->left = build(arrl, mid, node, 2 * cur_cnt + 1); // 左递归//
node->right = build(mid + 1, arrr, node, 2 * cur_cnt + 2);// 右递归//
node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
nodes[cur_cnt] = node;
return node;
}
};此时我们可以根据 SegTree 实例中的 nodes 成员查看区间信息。
区间查询
如果需要查询区间,那就将其分为几个极大区间处理,例如计算区间 a[1,5] 的和,那么就有区间:
a[1,5]=a[1]+a[2,3]+a[4,5]
也就是说我们只需要返回所有覆盖区间的值即可。
int query_sum(SegTreeNode *node, int ql, int qr)
{
if (!node || qr < node->l || ql > node->r)
return 0; // 完全不相交
if (ql <= node->l && node->r <= qr)
return node->self_sum_val; // 完全覆盖
// 部分相交,递归左右子树
return query_sum(node->left, ql, qr) + query_sum(node->right, ql, qr);
}从图上来看,这就是线段树的查找路径,蓝色部分为完全覆盖到区间:

单点修改只需要一直传给 parent 即可。
void point_set(int pos, int val)
{
int pre = arr[pos];
arr[pos] = val;
int adds = val - pre;
SegTreeNode *current = nodes[pos];
while (current != nullptr)
{
current->self_sum_val += adds;
current = current->parent;
}
}区间修改与懒标记
有同学说,如果到上面只需要单点修改,我还不如使用树状数组,常数小,代码短,那么线段树的优势就体现在快速区间修改上面。如果简单的对数组的每一个数进行修改,那么复杂度是 O(nlogn),速度很慢,那么我们就有必要引入一个懒标记,等到需要更新的的时候我们再进行更新数组。
接下来我们会对上面已经实现的线段树进行大改,引入懒标记和标记信息:
class SegTreeNode
{
public:
SegTreeNode() = default;
SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}
private:
int id;
int l, r;
SegTreeNode *parent;
int self_sum_val = 0;
SegTreeNode *left;
SegTreeNode *right;
bool has_lazy = false;
int lazy_add_val = 0;
friend class SegTree;
};然后我们讲一下原理,假设将 [3,5] 每个数值都加上 5,还是和刚刚一样自树根向下寻找极大覆盖区间,然后对这些区间打上懒标记。在递归向上传递的时候,顺带将路径上的所有值进行更新。如果是区间增加 x 的话,那么 lazy+=x,sum+=len×x,如果是区间统一改成 x。那么 lazy=x,sum=len×x,当计算到当前区间时,就向下传递懒标记。
下面图的部分表示搜索终点,即打上懒标记的点,部分表示在递归过程中同步进行修改的节点(注意部分无需懒标记)

当等到要查询的时候,如果当前递归访问的节点已经产生懒标记,就将懒标记向下推:我们举个例子:如果是将 [3,5] 每个数值都加上 5 后计算 a[0,6],在打懒标记查询极大区间的时候,我们在递归的时候就向上传递了信息此时无需向下传递懒标记,直接返回 tree[0] 就是结果。
那如果我们查询的是 a[1,4],其极大区间表示为:
a[1,4]=a[1]+a[2,3]+a[4]
其中递归到 a[4] 部分首先需要先递归到 a[4,5],但 a[4,5] 又有懒标记,所以我们在处理 a[4,5] 的时候,将懒标记下传到 a[4] 和 a[5],即如图所示:

然后在计算 a[4],继续下传,将懒标记的值加到自身,由于已经到低了,所以直接丢弃懒标记,此时懒标记只剩 a[5] 有 +5 懒标记。
这里我们代码以区间加为例,首先还是一样,递归查找极大覆盖区间:
void range_add_impl(SegTreeNode *node, int ql, int qr, int val)
{
if (!node || qr < node->l || ql > node->r)
return; // 不相交
if (ql <= node->l && node->r <= qr)
{
// 完全覆盖
node->self_sum_val += val * (node->r - node->l + 1);
node->lazy_add_val += val;
node->has_lazy = true;
return;
}
// 继续递归前先下推懒标记信息
push_down(node);
range_add_impl(node->left, ql, qr, val);
range_add_impl(node->right, ql, qr, val);
node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
}向下推懒标记:
void push_down(SegTreeNode *node)
{
if (!node || !node->has_lazy || node->l == node->r)
return;
int add = node->lazy_add_val;
// 左儿子
node->left->self_sum_val += add * (node->left->r - node->left->l + 1);
node->left->lazy_add_val += add;
node->left->has_lazy = true;
// 右儿子
node->right->self_sum_val += add * (node->right->r - node->right->l + 1);
node->right->lazy_add_val += add;
node->right->has_lazy = true;
// 清空当前节点懒标记
node->lazy_add_val = 0;
node->has_lazy = false;
}这样一个基础的区间修改,求和的线段树模板封装完毕!
Full Code
#include <bits/stdc++.h>
using namespace std;
class SegTree;
class SegTreeNode
{
public:
SegTreeNode() = default;
SegTreeNode(int nid) : id(nid), parent(nullptr), left(nullptr), right(nullptr) {}
private:
int id;
int l, r;
SegTreeNode *parent;
int self_sum_val = 0; // 区间信息,这里指的是 sum
SegTreeNode *left;
SegTreeNode *right;
bool has_lazy = false;
int lazy_add_val = 0;
friend class SegTree;
};
class SegTree
{
public:
SegTree(const vector<int> &v)
{
n = v.size();
arr = v;
nodes.resize(4 * n, nullptr);
root = build(0, n - 1, nullptr, 0);
}
int range_sum(int l, int r) { return query_sum(root, l, r); }
void range_add(int l, int r, int val) { range_add_impl(root, l, r, val); }
private:
int n;
SegTreeNode *root;
vector<int> arr;
vector<SegTreeNode *> nodes;
SegTreeNode *build(int arrl, int arrr, SegTreeNode *parent, int cur_cnt)
{
SegTreeNode *node = new SegTreeNode(cur_cnt);
node->parent = parent;
node->l = arrl;
node->r = arrr;
if (arrl == arrr) // 叶子节点
{
node->self_sum_val = arr[arrl];
node->left = node->right = nullptr;
nodes[cur_cnt] = node;
return node;
}
int mid = (arrl + arrr) / 2;
node->left = build(arrl, mid, node, 2 * cur_cnt + 1);
node->right = build(mid + 1, arrr, node, 2 * cur_cnt + 2);
node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
nodes[cur_cnt] = node;
return node;
}
int query_sum(SegTreeNode *node, int ql, int qr)
{
if (!node || qr < node->l || ql > node->r)
return 0; // 完全不相交
if (ql <= node->l && node->r <= qr)
return node->self_sum_val; // 完全覆盖
// 部分相交,递归左右子树
return query_sum(node->left, ql, qr) + query_sum(node->right, ql, qr);
}
void range_add_impl(SegTreeNode *node, int ql, int qr, int val)
{
if (!node || qr < node->l || ql > node->r)
return; // 不相交
if (ql <= node->l && node->r <= qr)
{
node->self_sum_val += val * (node->r - node->l + 1);
node->lazy_add_val += val;
node->has_lazy = true;
return;
}
// 继续递归前先下推
push_down(node);
range_add_impl(node->left, ql, qr, val);
range_add_impl(node->right, ql, qr, val);
node->self_sum_val = node->left->self_sum_val + node->right->self_sum_val;
}
void push_down(SegTreeNode *node)
{
if (!node || !node->has_lazy || node->l == node->r)
return;
int add = node->lazy_add_val;
// 左儿子
node->left->self_sum_val += add * (node->left->r - node->left->l + 1);
node->left->lazy_add_val += add;
node->left->has_lazy = true;
// 右儿子
node->right->self_sum_val += add * (node->right->r - node->right->l + 1);
node->right->lazy_add_val += add;
node->right->has_lazy = true;
// 清空当前节点懒标记
node->lazy_add_val = 0;
node->has_lazy = false;
}
};