(精华)2020年8月27日 数据结构与算法解析(线段树)
/// <summary>
/// 线段树:线段树是二叉树的一种,常常被用于求区间和与区间最大值等操作
/// </summary>
public class SegmentTree
{
List<int> _orignalData = new List<int>();
List<int?> _tree = new List<int?>();
public SegmentTree()
{
for (int i = 0; i < 1000; i++)
{
_tree.Add(null);
}
}
public void Print()
{
for (int i = 0; i < _tree.Count; i++)
{
if (_tree[i] == null)
{
continue;
}
Console.WriteLine($"第{i}:{_tree[i]}");
}
}
public void Fill(List<int> data)
{
_orignalData = data;
Fill(0, 0, _orignalData.Count - 1);
}
private void Fill(int node, int start, int end)
{
if (start == end)
{
_tree[node] = _orignalData[start];
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
Fill(leftNode, start, mid);
Fill(rightNode, mid + 1, end);
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public void Set(int index, int val)
{
SetValue(0, 0, _orignalData.Count - 1, index, val);
}
private void SetValue(int node, int start, int end, int index, int val)
{
if (start == end)
{
_orignalData[index] = val;
_tree[node] = val;
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
if (index >= start && index <= mid)
{
SetValue(leftNode, start, mid, index, val);
}
else
{
SetValue(rightNode, mid + 1, end, index, val);
}
_tree[node] = _tree[leftNode] + _tree[rightNode];
}
}
public int? GetSum(int left, int right)
{
return Query(0, 0, _orignalData.Count - 1, left, right);
}
private int? Query(int node, int start, int end, int left, int right)
{
if (right < start || left > end)
{
return 0;
}
else if (left <= start && end <= right)
{
return _tree[node];
}
else if (start == end)
{
return _tree[node];
}
else
{
int mid = (start + end) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
int? sumLeft = Query(leftNode, start, mid, left, right);
int? sumRight = Query(rightNode, mid + 1, end, left, right);
return sumLeft + sumRight;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
原理
（注：由于线段树的每个节点代表一个区间，以下叙述中不区分节点和区间，只是根据语境需要，选择合适的词）
线段树本质上是维护下标为1,2,…,n的n个按顺序排列的数的信息，所以，其实是“点树”，是维护n的点的信息，至于每个点的数据的含义可以有很多，
在对线段操作的线段树中，每个点代表一条线段，在用线段树维护数列信息的时候，每个点代表一个数，但本质上都是每个点代表一个数。以下，在讨论线段树的时候，区间[L,R]指的是下标从L到R的这(R-L+1)个数，而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。
线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法，即对结果下取整)直到 L==R 为止。
开始时是区间[1,n] ,通过递归来逐步分解，假设根的高度为1的话，树的最大高度为（n>1）。
线段树对于每个n的分解是唯一的，所以n相同的线段树结构相同，这也是实现可持久化线段树的基础。
下图展示了区间[1,13]的分解过程：
上图中，每个区间都是一个节点，每个节点存自己对应的区间的统计信息。
(1)线段树的点修改：
假设要修改[5]的值，可以发现，每层只有一个节点包含[5],所以修改了[5]之后，只需要每层更新一个节点就可以线段树每个节点的信息都是正确的，所以修改次数的最大值为层数。
复杂度O(log2(n))
(2)线段树的区间查询：
线段树能快速进行区间查询的基础是下面的定理：
定理：n>=3时，一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。
这样，在查询[L,R]的统计值的时候，只需要访问不超过个节点，就可以获得[L,R]的统计信息，实现了O(log2(n))的区间查询。
下面给出证明：
(2.1)先给出一个粗略的证明（结合下图）：
先考虑树的最下层，将所有在区间[L,R]内的点选中，然后，若相邻的点的直接父节点是同一个，那么就用这个父节点代替这两个节点（父节点在上一层）。这样操作之后，本层最多剩下两个节点。若最左侧被选中的节点是它父节点的右子树，那么这个节点会被剩下。若最右侧被选中的节点是它的父节点的左子树，那么这个节点会被剩下。中间的所有节点都被父节点取代。
对最下层处理完之后，考虑它的上一层，继续进行同样的处理，可以发现，每一层最多留下2个节点，其余的节点升往上一层，这样可以说明分割成的区间（节点）个数是大概是树高的两倍左右。
下图为n=13的线段树，区间[2,12]，按照上面的叙述进行操作的过程图：
由图可以看出：在n=13的线段树中，[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。
(2.2)然后给出正式一点的证明：
定理：n>=3时，一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。
用数学归纳法，证明上面的定理：
首先,n=3,4,5时，用穷举法不难证明定理成立。
假设对于n= 3,4,5,…,k-1上式都成立，下面来证明对于n=k ( k>=6 )成立：
分为4种情况来证明：
情况一：[L,R]包含根节点(L=1且R=n)，此时，[L,R]被分解为了一个节点，定理成立。
情况二：[L,R]包含根节点的左子节点，此时[L,R]一定不包含根的右子节点（因为如果包含，就可以合并左右子节点，
用根节点替代，此时就是情况一）。这时，以右子节点为根的这个树的元素个数为。
[L,R]分成的子区间由两部分组成：
一：根的左子结点，区间数为1
二：以根的右子节点为根的树中，进行区间查询，这个可以递归使用本定理。
由归纳假设可得，[L,R]一共被分成了个区间。
情况三：跟情况二对称，不一样的是，以根的左子节点为根的树的元素个数为。
[L,R]一共被分成了个区间。
从公式可以看出，情况二的区间数小于等于情况三的区间数，于是只需要证明情况三的区间数符合条件就行了。
于是，情况二和情况三定理成立。
情况四：[L,R]不包括根节点以及根节点的左右子节点。
于是，剩下的层，每层最多两个节点（参考粗略证明中的内容）。
于是[L,R]最多被分解成了个区间，定理成立。
上面只证明了是上界，但是，其实它是最小上界。
n=3,4时，有很多组区间的分解可以达到最小上界。
当n>4时，当且仅当n=2^t (t>=3),L=2,R=2^t -1 时，区间[L,R]的分解可以达到最小上界。
就不证明了，有兴趣可以自己去证明。
下图是n=16 , L=2 , R=15 时的操作图，此图展示了达到最小上界的树的结构。
(3)线段树的区间修改：
线段树的区间修改也是将区间分成子区间，但是要加一个标记，称作懒惰标记。
标记的含义：
本节点的统计信息已经根据标记更新过了，但是本节点的子节点仍需要进行更新。
即，如果要给一个区间的所有值都加上1，那么，实际上并没有给这个区间的所有值都加上1，而是打个标记，记下来，这个节点所包含的区间需要加1.打上标记后，要根据标记更新本节点的统计信息，比如，如果本节点维护的是区间和，而本节点包含5个数，那么，打上+1的标记之后，要给本节点维护的和+5。这是向下延迟修改，但是向上显示的信息是修改以后的信息，所以查询的时候可以得到正确的结果。有的标记之间会相互影响，所以比较简单的做法是，每递归到一个区间，首先下推标记（若本节点有标记，就下推标记），然后再打上新的标记，这样仍然每个区间操作的复杂度是O(log2(n))。
标记有相对标记和绝对标记之分：
相对标记是将区间的所有数+a之类的操作，标记之间可以共存，跟打标记的顺序无关（跟顺序无关才是重点）。
所以，可以在区间修改的时候不下推标记，留到查询的时候再下推。
注意：如果区间修改时不下推标记，那么PushUp函数中，必须考虑本节点的标记。
而如果所有操作都下推标记，那么PushUp函数可以不考虑本节点的标记，因为本节点的标记一定已经被下推了（也就是对本节点无效了）
绝对标记是将区间的所有数变成a之类的操作，打标记的顺序直接影响结果，
所以这种标记在区间修改的时候必须下推旧标记，不然会出错。
注意，有多个标记的时候，标记下推的顺序也很重要，错误的下推顺序可能会导致错误。
之所以要区分两种标记，是因为非递归线段树只能维护相对标记。
因为非递归线段树是自底向上直接修改分成的每个子区间，所以根本做不到在区间修改的时候下推标记。
非递归线段树一般不下推标记，而是自下而上求答案的过程中，根据标记更新答案。
(4)线段树的存储结构：
线段树是用数组来模拟树形结构，对于每一个节点R ,左子节点为 2R (一般写作R<<1)右子节点为 2R+1（一般写作R<<1|1）
然后以1为根节点，所以，整体的统计信息是存在节点1中的。
这么表示的原因看下图就很明白了，左子树的节点标号都是根节点的两倍，右子树的节点标号都是左子树+1：
线段树需要的数组元素个数是：,一般都开4倍空间，比如： int A[n<<2];
文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。
原文链接：codeboy.blog.csdn.net/article/details/108189020
- 点赞
- 收藏
- 关注作者
评论（0）