线段树详解（含代码实现经过测试）
⽬录
1.线段树介绍
什么是线段树？线段树是⼀种，与相似，它将⼀个区间划分成⼀些单元区间，每个单元区间对应线段树中的⼀个叶结点。 [1]
对于线段树中的每⼀个⾮[a,b]，它的左⼉⼦表⽰的区间为[a,(a+b)/2]，右⼉⼦表⽰的区间为[(a+b)/2+1,b]。因此线段树是，最后的⼦节点数⽬为N，即整个线段区间的长度。
使⽤线段树可以快速的查某⼀个节点在若⼲条线段中出现的次数，为O(logN）。⽽未优化的为2N，因此有时需要离散化让空间压缩。-----来⾃百度。
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.线段树的构建对应代码：
1#pragma once
2#include<iostream>
3#include<vector>
4using std::vector;
5using std::cout;
6using std::endl;
7class SegmentTree {
8public:
9 SegmentTree(const vector<int>& origin) {
10  MAXN = origin.size() + 1;
11  size(MAXN);
12  for (int i = 1; i < MAXN; i++) {//arr[0]不⽤从arr[1]开始
13  arr[i] = origin[i - 1];
14  }
15  size(MAXN << 2);//相当与MAXN*4；⽤来⽀持脑补概念中，某⼀个范围的累加和信息
16  size(MAXN << 2);//⽤来⽀持脑补概念中，某⼀个没有在往下的累加和标记
17  size(MAXN << 2);
18  size(MAXN << 2);
19
20 }
21 void build(int l, int r, int rt) {
22  if (l == r) {//只有⼀个数
23  sum[rt] = arr[l];
24  return;
25  }
26  int mid = (l + r) >> 1;
27  build(l, mid, rt << 1);
28  build(mid + 1, r, (rt << 1) | 1);//相当于2*rt+1;
29  pushUp(rt);//计算玩向上返回累加和
30 };
31 void pushUp(int rt) {
32  sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];//rt<<1|1相当于2*rt+1;
33 }
34private:
35 int MAXN;
36 vector<int>arr;//arr维护的是原序列信息从0开始，但是在这⾥arr从1开始
37 vector<int>sum;//模拟线段树维护区间和
38 vector<int>lazy;//为累加懒惰信息标记
39 vector<int>change;//对应位置的更新值
40 vector<bool>update;//为更新懒惰标记
41};
2.1区间修改
修改⼤概可以分为两步：
1.到这段区间。
2.修改这⼀区间所有的点
⼤致流程如下：
1.如果当前区间完全被覆盖在⽬标区间⾥将这个区间sum数组的的位置加上（r-l+1)*C
2.如果没有完全覆盖则先下传懒标记
3.如果这个区间的左孩⼦和⽬标区间有交集，那么就递归给左孩⼦分配任务
4.如果这个区间的右孩⼦和⽬标区间有交集，则递归分配任务给右孩⼦。
懒更新：
下传标记
碰到 相对标记 这种容易欺负的⼩朋友，我们只⽤打⼀下懒惰标记就可以了。
但是，遇到 绝对标记 ，或是下⽂提到的 区间查询 ，简单地打上懒惰标记就明显GG了。毕竟， 懒惰标记 只是简单地在节点挂上⼀个信息⽽已，遇到复杂的情况可是不⾏的啊！
于是，懒惰标记的 下传操作 就诞⽣了。
顾名思义， 下传标记 就是把⼀个节点的懒惰标记传给它的左右⼉⼦，再把该节点的懒惰标记删去。
我们先来回顾⼀下标记的含义：
标记的含义：本区间已经被更新过了，但是⼦区间却没有被更新过，被更新的信息是什么。
显然，⽗区间是包含⼦区间的，也就是对于⽗区间的标记和⼦区间是有联系的。在⼤多数情况下，⽗区间和⼦区间的标记是 相同的 。
因此，我们可以由⽗区间的标记推算出⼦区间应当是什么标记。
注意：以下所说的问题都是指区间赋值，除⾮有什么特别的申明。
如果要给⼀个节点中的所有元素重新赋值为 x  ，那么它的⼉⼦也必定要被赋值成 x  。所以，我们直接在⼦节点处修改  sumsum 值，再把⼦节点的标记改变⼀下就可以了（由于区间赋值要⽤ 绝对标记 ，因此当⼦节点已经有标记时，要先下传⼦节点的标记，再下传该节点的标记。但是区间赋值会覆盖掉⼦节点的值，因此在这个问题中，直接修改标记就可以了）
下⾯是在对应区间加C的代码：
1void pushUp(int rt) {//更新⽗亲的累加和
2  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
3 }
4 void pushDown(int rt, int ln, int rn) {
5  if (update[rt]) {//update⽅法需要使⽤
6  update[rt << 1] = true;//往下发
7  update[rt << 1|1] = true;
8  change[rt << 1] = change[rt];
9  change[rt << 1 | 1] = change[rt];
10  lazy[rt << 1] = 0;//清空左右孩⼦的懒数组
11  lazy[rt << 1 | 1] = 0;
12  sum[rt << 1] = change[rt] * ln;//左孩⼦总和
13  sum[rt << 1 | 1] = change[rt] * rn;//右孩⼦总和
14  update[rt] = false;//当前位置已经下发改成false;
15  }
16  if (lazy[rt]) {
17  lazy[rt << 1] += lazy[rt];
18  lazy[(rt << 1) | 1] += lazy[rt];
19  sum[rt << 1] += lazy[rt] * ln;
20  sum[rt << 1 | 1] += lazy[rt] * rn;
21  lazy[rt] = 0;
二叉树公式
22  }
23 }
24 void add(int L, int R, int C, int l, int r, int rt) {//L和R表⽰实际要修改的范围 l到r表⽰实际的范围 rt 表⽰这个范围
25  //的信息我去数组中那个位置去
26  if (L <= l && r <= R) {//懒住
27  //修改相关信息
28  sum[rt] += C * (r - l + 1);
29  lazy[rt] += C;
30  return;
31  }
32  //当前任务躲不掉，⽆法懒更新，要往下发
33  int mid = (l + r) >> 1;
34  pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩⼦
35  if (L <= mid) {//左孩⼦需要下发任务
36  add(L, R, C, l, mid, rt << 1);
37  }
38  if (R > mid) {//右孩⼦需要下发任务
39  add(L, R, C, mid + 1, r, rt << 1 | 1);
40  }
41  pushUp(rt);//更新⽗亲的累加和
42 }
对于add中的参数解释：
1.L，R代表要修改的区间范围
2.l,r 代表实际的范围
3.C要加的值
<表⽰l到r位置对于的信息在数组的那个位置去拿
对于pushdown⽅法的解释：
1.包括了update⽅法的和add的懒操作
2.2区间查询

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。