# 【愚公系列】2021年11月 C#版 数据结构与算法解析(线段树)

+关注继续查看
/// <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)线段树的区间查询：

(2.1)先给出一个粗略的证明（结合下图）：

(2.2)然后给出正式一点的证明：

[L,R]分成的子区间由两部分组成：

[L,R]一共被分成了个区间。

n=3,4时，有很多组区间的分解可以达到最小上界。

3)线段树的区间修改：

(4)线段树的存储结构：

7251 0

338 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(交换排序-冒泡排序)
【愚公系列】2021年11月 C#版 数据结构与算法解析(交换排序-冒泡排序)
3 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(分块查找)
【愚公系列】2021年11月 C#版 数据结构与算法解析(分块查找)
3 0

8947 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(AVL树)
14 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(Trie树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(Trie树)
10 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(线段树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(线段树)
13 0
【愚公系列】2021年11月 C#版 数据结构与算法解析 for和foreach性能分析
【愚公系列】2021年11月 C#版 数据结构与算法解析 for和foreach性能分析
11 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(树)
【愚公系列】2021年11月 C#版 数据结构与算法解析(树)
7 0
+关注

150

0

《Nacos架构&原理》

《看见新力量：二》电子书