1.线段树介绍
什么是线段树？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 [1]
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。-----来自百度。
2.线段树原理及其实现
线段树主要是把一段大区间 平均地划分 成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 log 级别（因为这棵线段树是平衡的）。也就是说一个[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,R]这两个小区间。然后再递归下去分直达L=R。
下图就是一棵 [ 1 , 10 ] 的线段树的分解过程（相同颜色的节点在同一层）如图所示：
我们可以发现，这棵线段树的最大深度不超过[ log2 ( n − 1 ) ]+2.
1.实现的基本框架
我们如何实现这种结构呢？难道真的是用二叉树吗？当然不是我们可以用我们之前学过的堆来实现这种结构。本文中使用满二叉树来实现线段树，可能有老铁会问了如果给定数组的长度不是2的某次方时又该怎么办了？在这里如果他不是满二叉树我们给他补成满二叉树。
2.空间的计算
实现线代树我采用了大根堆来实现，这是因为大根堆是一个完全二叉树因此我们可以使用数组来表示，只不过当数组的长度不是2^i时我们需要补齐。如图所示
现在我们来估计一下大概需要多少空间。假设区间有n个元素，对于满二叉树来说：
1.第一层到第k层一共有2^k-1个节点（约有2^k）个节点
2.最后一层共有2^k-1个节点
我们可以得出：满二叉树中最后一层节点的个数大约是前面节点的个数之和
1.如果n=2^i则需要2n个节点
2.如果n=2^i+1时此时情况最坏需要4*n个节点（估计值）
3.表示方式：
在这里我们我们数组的下标是从1开始，这是为了让左右孩子的下标能够使用位运算来进而提高效率。如果一个父亲节点对应的索引为i那么则有下面公式：
1.左孩子=2*i;
2.右孩子=2*i+1
用位运算来表示为：
1.左孩子=i<<1;
2.右孩子=i<<1|1;
4.线段树的构建对应代码：
#pragma once #include<iostream> #include<vector> using std::vector; using std::cout; using std::endl; class SegmentTree { public: SegmentTree(const vector<int>& origin) { MAXN = origin.size() + 1; arr.resize(MAXN); for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始 arr[i] = origin[i - 1]; } sum.resize(MAXN << 2);//相当与MAXN*4；用来支持脑补概念中，某一个范围的累加和信息 lazy.resize(MAXN << 2);//用来支持脑补概念中，某一个没有在往下的累加和标记 change.resize(MAXN << 2); update.resize(MAXN << 2); } void build(int l, int r, int rt) { if (l == r) {//只有一个数 sum[rt] = arr[l]; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, (rt << 1) | 1);//相当于2*rt+1; pushUp(rt);//计算玩向上返回累加和 }; void pushUp(int rt) { sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];//rt<<1|1相当于2*rt+1; } private: int MAXN; vector<int>arr;//arr维护的是原序列信息从0开始，但是在这里arr从1开始 vector<int>sum;//模拟线段树维护区间和 vector<int>lazy;//为累加懒惰信息标记 vector<int>change;//对应位置的更新值 vector<bool>update;//为更新懒惰标记 };
2.1区间修改
修改大概可以分为两步：
1.找到这段区间。
2.修改这一区间所有的点
大致流程如下：
1.如果当前区间完全被覆盖在目标区间里将这个区间sum数组的的位置加上（r-l+1)*C
2.如果没有完全覆盖则先下传懒标记
3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务
4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。
懒更新：
在线段树中为了提高效率引入了懒跟新：
1.标记的含义：区间已经被更新过，但是子区间没有被更新过，被更新的信息是什么（区间求和只用记录有没有被访问过，而区间的四则运算等多种操作的问题则要记录是那一种操作）。
这里再引入两个很重要的东西：相对标记和绝对标记相对标记：指的是可以共存的标记，且打标记的顺序与答案无关，即标记可以叠加。 比如说给一段区间中的所有数字都 + a ，我们就可以把标记叠加一下，比如上一次打了一个 加2 的标记，这一次要给这一段区间 +5 ，那么就把 + 2 的标记变成 + 5
绝对标记：
是指不可以共存的标记，每一次都要先把标记下传，再给当前节点打上新的标记。这些标记不能改变次序，否则会出错。 比如说给一段区间的数字重新赋值，或是给一段区间进行多种操作。
例如：
有了 懒惰标记 这种神奇的东西，我们区间修改时就可以偷一下懒，先修改当前节点，然后直接把信息挂在节点上就可以了！
如下面这棵线段树，当我们要修改区间 [ 1 , 4 ] [1,4][1,4] ，将元素赋值为 1 时，我们可以先找到所有的整个区间都要被修改的节点，显然是储存区间 [1,3] 和 [4,4] 的这两个节点。我们就可以先把 [1,3] 的 sum 改为(3−1+1)∗1=3 ,把 [ 4 , 4 ] 的 sum 改为 (1-1+1)*1=1 ，然后给它们打上值为 1 的懒惰标记，然后就可以了。
这样一来，我们每一次修改区间时只要找到目标区间就可以了，不用再向下递归到叶节点，从而提高了效率。
下传标记
碰到 相对标记 这种容易欺负的小朋友，我们只用打一下懒惰标记就可以了。
但是，遇到 绝对标记 ，或是下文提到的 区间查询 ，简单地打上懒惰标记就明显GG了。毕竟， 懒惰标记 只是简单地在节点挂上一个信息而已，遇到复杂的情况可是不行的啊！
于是，懒惰标记的 下传操作 就诞生了。
顾名思义， 下传标记 就是把一个节点的懒惰标记传给它的左右儿子，再把该节点的懒惰标记删去。
我们先来回顾一下标记的含义：标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么。
显然，父区间是包含子区间的，也就是对于父区间的标记和子区间是有联系的。在大多数情况下，父区间和子区间的标记是 相同的 。因此，我们可以由父区间的标记推算出子区间应当是什么标记。
注意：以下所说的问题都是指区间赋值，除非有什么特别的申明。
如果要给一个节点中的所有元素重新赋值为 x ，那么它的儿子也必定要被赋值成 x 。所以，我们直接在子节点处修改 sumsum 值，再把子节点的标记改变一下就可以了（由于区间赋值要用 绝对标记 ，因此当子节点已经有标记时，要先下传子节点的标记，再下传该节点的标记。但是区间赋值会覆盖掉子节点的值，因此在这个问题中，直接修改标记就可以了）
下面是在对应区间加C的代码：
void pushUp(int rt) {//更新父亲的累加和 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushDown(int rt, int ln, int rn) { if (update[rt]) {//update方法需要使用 update[rt << 1] = true;//往下发 update[rt << 1|1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; lazy[rt << 1] = 0;//清空左右孩子的懒数组 lazy[rt << 1 | 1] = 0; sum[rt << 1] = change[rt] * ln;//左孩子总和 sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和 update[rt] = false;//当前位置已经下发改成false; } if (lazy[rt]) { lazy[rt << 1] += lazy[rt]; lazy[(rt << 1) | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * ln; sum[rt << 1 | 1] += lazy[rt] * rn; lazy[rt] = 0; } } void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围 //的信息我去数组中那个位置去找 if (L <= l && r <= R) {//懒住 //修改相关信息 sum[rt] += C * (r - l + 1); lazy[rt] += C; return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子 if (L <= mid) {//左孩子需要下发任务 add(L, R, C, l, mid, rt << 1); } if (R > mid) {//右孩子需要下发任务 add(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲的累加和 }
对于add中的参数解释：
1.L，R代表要修改的区间范围
2.l,r 代表实际的范围
3.C要加的值
4.rt表示l到r位置对于的信息在数组的那个位置去拿
对于pushdown方法的解释：
1.包括了update方法的和add的懒操作
2.2区间查询
区间查询的和add基本类似：
1.如果当前区间完全被覆盖在目标区间里将对于sum位置的数据返回
2.如果没有完全覆盖则先下传懒标记
3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务
4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。
对应代码：
long long query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值 return sum[rt]; } int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子 long long ans = 0; if (L <= mid) { ans+=query(L, R, l, mid, rt << 1); } if (R > mid) { ans += query(L, R, mid + 1, r, rt << 1 | 1); } return ans; }
2.3区间更新
区间更新和区间的修改也是基本类似但也所不同
1.如果某一个区间被设置成对应的数那么该区间的lazy数组中的数据全部置为0
2.如果当前区间懒不住要先下发懒信息给左右孩子在分配任务
具体请看代码：
void Update(int L, int R, int C, int l, int r, int rt) { if (L <= l && r <= R) { update[rt] = true;//标记已经更新过 change[rt] = C; sum[rt] = C * (r - l + 1); lazy[rt] = 0;//清空 return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid); if (L <= mid) { Update(L, R, C, l, mid, rt << 1); } if (R > mid) { Update(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲节点的累加和 }
对应总代码：
#pragma once #include<iostream> #include<vector> using std::vector; using std::cout; using std::endl; class SegmentTree { public: SegmentTree(const vector<int>& origin) { MAXN = origin.size() + 1; arr.resize(MAXN); for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始 arr[i] = origin[i - 1]; } sum.resize(MAXN << 2);//相当与MAXN*4；用来支持脑补概念中，某一个范围的累加和信息 lazy.resize(MAXN << 2);//用来支持脑补概念中，某一个没有在往下的累加和标记 change.resize(MAXN << 2); update.resize(MAXN << 2); } void build(int l, int r, int rt) { if (l == r) { sum[rt] = arr[l]; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1); build(mid + 1, r, rt << 1 | 1);//相当于2*rt+1; pushUp(rt); }; void pushUp(int rt) {//更新父亲的累加和 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushDown(int rt, int ln, int rn) { if (update[rt]) {//update方法需要使用 update[rt << 1] = true;//往下发 update[rt << 1|1] = true; change[rt << 1] = change[rt]; change[rt << 1 | 1] = change[rt]; lazy[rt << 1] = 0;//清空左右孩子的懒数组 lazy[rt << 1 | 1] = 0; sum[rt << 1] = change[rt] * ln;//左孩子总和 sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和 update[rt] = false;//当前位置已经下发改成false; } if (lazy[rt]) {//下发懒信息 lazy[rt << 1] += lazy[rt]; lazy[(rt << 1) | 1] += lazy[rt]; sum[rt << 1] += lazy[rt] * ln; sum[rt << 1 | 1] += lazy[rt] * rn; lazy[rt] = 0; } } void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围 //的信息我去数组中那个位置去找 if (L <= l && r <= R) {//懒住 //修改相关信息 sum[rt] += C * (r - l + 1); lazy[rt] += C; return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子 if (L <= mid) {//左孩子需要下发任务 add(L, R, C, l, mid, rt << 1); } if (R > mid) {//右孩子需要下发任务 add(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲的累加和 } void Update(int L, int R, int C, int l, int r, int rt) { if (L <= l && r <= R) { update[rt] = true;//标记已经更新过 change[rt] = C; sum[rt] = C * (r - l + 1); lazy[rt] = 0;//清空 return; } //当前任务躲不掉，无法懒更新，要往下发 int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid); if (L <= mid) { Update(L, R, C, l, mid, rt << 1); } if (R > mid) { Update(L, R, C, mid + 1, r, rt << 1 | 1); } pushUp(rt);//更新父亲节点的累加和 } long long query(int L, int R, int l, int r, int rt) { if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值 return sum[rt]; } int mid = (l + r) >> 1; pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子 long long ans = 0; if (L <= mid) { ans+=query(L, R, l, mid, rt << 1); } if (R > mid) { ans += query(L, R, mid + 1, r, rt << 1 | 1); } return ans; } private: int MAXN; vector<int>arr;//arr维护的是原序列信息从0开始，但是在这里arr从1开始 vector<int>sum;//模拟线段树维护区间和 vector<int>lazy;//为累加懒惰信息标记 vector<int>change;//对应位置的更新值 vector<bool>update;//为更新懒惰标记 };
上述代码博主经过测试基本正确如有错误请在评论区留言！
版权归原作者 一个山里的少年 所有， 如有侵权，请联系我们删除。