线段树详解 原理解释 + 构建步骤 + 代码（带模板）

目录

介绍：    

定义：

以具体一个题目为例：​

树的表示方法：

实现步骤：

构建结点属性：

pushup函数：

build函数：

pushdown函数：

modify函数：

query函数：

如何记忆：

模板：

---

介绍：    

        线段树（Segment Tree）是一种常用的数据结构，用于解决涉及区间查询的问题。它主要用于在数组或列表等数据结构上支持以下两类查询操作：

1. 区间查询：查询某个区间内的统计信息，例如求和、最大值、最小值等。
2. 区间更新：修改数组中某个区间元素的值，并相应地更新线段树中的信息。

        核心思想是将原始数据递归地划分成一系列不相交的区间，并在每个区间上维护一些预先计算好的信息，以支持高效的区间查询。

定义：

        假设我们有一个包含 N 个元素的数组 A，线段树 T 是基于数组 A 的线段树。线段树 T 是一个满二叉树，它具有以下性质：

1. 根节点表示整个数组的区间 [1, N]。
2. 如果一个节点表示的区间是 [left, right]，则它的左子节点表示的区间是 [left, mid]，右子节点表示的区间是 [mid+1, right]，其中 mid 是 left 和 right 的中间值。
3. 叶子节点表示数组 A 中的单个元素，而内部节点表示对应区间上的预计算信息（如区间和、区间最大值等）。
4. 线段树通常使用数组来模拟实现。

线段树算法一般包含以下五个函数：

        1.build(); 初始构建一个线段树。

        2.pushpu(); 向上传递信息。

        3.pushdown(); 向下传递懒标记，并且更新子树。

        4.modify(); 修改某一区间。

        5.query(); 查询某一区间信息。

下面我们一个一个来介绍。 

以具体一个题目为例：

下面解析以此题目为例子。

树的表示方法：

        我们用 tr 数组来模拟这颗树。

        假设根节点在 tr 数组中的的下标为为 i，那么其左右子树的下标为：

                左：i * 2 (i << 1)

                右：i * 2 + 1 (i << 1 | 1)

        我们一般使用位运算，也就是括号里的，含义是一样的。所以可以计算出，tr 数组的长度最多就是题目所给数组长度的4倍。

实现步骤：

事先把输入的数组存在 w数组 中。

构建结点属性：

        树结点其实就是一个区间，所以属性包含：左右边界，懒标记。

        此题的懒标记就是区间需要加上的值 d 。

        根据题目我们还需要查询区间的元素和，所以在其中添加一个 sum。

struct Node
{int l, r;LL sum;LL add; // 懒标记
}tr[N * 4];;

pushup函数：

        我们在 build 一颗树之前，要先写 pushup 函数，用于向上传递信息，因为我们只知道叶子结点的值，我们要用后序遍历去构建父亲，所以要用到 pushup ，根据题目，我们要向上传递的信息显然是左右子树的 sum 和，这样就可以算出父亲的 sum 。

void pushup(int u) // 向上传递信息
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

build函数：

        接下来我们开始构建这颗树，若区间内只有一个元素（l == r），说明我们找到了叶子结点，给叶子结点赋值，若不是结子节点（l != r），就继续向左右子树递归，在递归完成时（后序遍历）使用pushup，通过已经获得值的子树去更新父亲。

void build(int u, int l, int r)
{if (l == r) tr[u] = {l, r, w[l], 0}; // 叶子节点else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 若不是叶子节点，向下递归pushup(u); // 通过子树构建父亲}
}

pushdown函数：

        pushdown函数是给子树传递懒标记的，如果懒标记不为空，就将父亲的懒标记传递给左右子树，并且通过懒标记更新左右子树的信息，此题求的是sum，所以子树的 sum 值就要加上区间长度乘上父亲的懒标记，最后清空父亲的懒标记。

        注意：懒标记表示的子树需要添加的信息，不包含父亲自己，所以在传递懒标记时，才要传递懒标记同时更新子树。

void pushdown(int u)
{auto &root = tr[u], &left = tr[u << 1], & right = tr[u << 1 | 1];if (root.add){// 传递懒标记并且更新子树left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;root.add = 0; // 删除懒标记}
}

modify函数：

        修改区间信息，如果当前遍历的结点区间已经在区间中，那么就直接给其加上懒标记，并且计算更新其 sum。如果当前遍历的结点区间中的一部分是需要修改的区间，那么就先向下传递懒标记pushdown，然后在向需要修改的左右子树去递归，后序返回时，要给更新父亲pushup。

void modify(int u, int l, int r, int v)
{// 结点在要修改的区间中if (l <= tr[u].l && r >= tr[u].r){tr[u].sum += (tr[u].r - tr[u].l + 1) * v;tr[u].add += v; // 加上懒标记}else{pushdown(u); // 先传递懒标记int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, v);if (r > mid) modify(u << 1 | 1, l, r, v);pushup(u); // 更新父亲}
}

query函数：

        用于查询区间信息，这里就是查询区间的sum。若遍历到的结点区间在查询区间之中，就返回其sum，若结点区间只有一部分在查询区间中，一样的，也是先传递懒标记，然后继续向需要计算的左右子树去递归，后序返回时计算结果。

LL query(int u, int l, int r)
{if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; // 返回区间信息pushdown(u); // 也是先传递懒标记LL v = 0;int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) v = query(u << 1, l, r);if (r > mid) v += query(u << 1 | 1, l, r);return v;
}

如何记忆：

        最重要的是注意每个函数pushup，pushdown函数的位置。只有在modify函数才两个一起用。

build函数只用一个pushup，query函数只用一个pushdown。

模板：

根据具体题目，自行修改。

// 操作是给区间每一个数加d
// 询问是求某一区间和
#include<iostream>using namespace std;typedef long long LL;
const int N = 100010;int w[N];
int n, m;struct Node
{int l, r;LL sum;LL add; // 懒标记
}tr[N * 4];;void pushup(int u) // 向上传递信息
{tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{auto &root = tr[u], &left = tr[u << 1], & right = tr[u << 1 | 1];if (root.add){// 传递懒标记并且更新子树left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;root.add = 0; // 删除懒标记}
}
void build(int u, int l, int r)
{if (l == r) tr[u] = {l, r, w[l], 0}; // 叶子节点else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 若不是叶子节点，向下递归pushup(u); // 通过子树构建父亲}
}
void modify(int u, int l, int r, int v)
{// 结点在要修改的区间中if (l <= tr[u].l && r >= tr[u].r){tr[u].sum += (tr[u].r - tr[u].l + 1) * v;tr[u].add += v; // 加上懒标记}else{pushdown(u); // 先传递懒标记int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, v);if (r > mid) modify(u << 1 | 1, l, r, v);pushup(u); // 更新父亲}
}LL query(int u, int l, int r)
{if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum; // 返回区间信息pushdown(u); // 也是先传递懒标记LL v = 0;int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) v = query(u << 1, l, r);if (r > mid) v += query(u << 1 | 1, l, r);return v;
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]); // 读入数组build(1, 1, n); // 以1为根节点，1~n区间建树char op[2];int l, r, t;// 读入修改和查询，q是查询，否则是修改while (m -- ){scanf("%s%d%d", op, &l, &r);if (*op == 'Q') printf("%lld\n", query(1, l, r));else{scanf("%d", &t);modify(1, l, r, t);}}return 0;
}