CShap 实现线段树 源代码
时间: 2023-11-14 14:14:43 浏览: 35
以下是C#实现线段树的源代码:
```csharp
using System;
public class SegmentTree
{
private int[] tree;
private int[] nums;
public SegmentTree(int[] nums)
{
this.nums = nums;
this.tree = new int[4 * nums.Length];
BuildTree(0, 0, nums.Length - 1);
}
private void BuildTree(int node, int start, int end)
{
if (start == end)
{
tree[node] = nums[start];
}
else
{
int mid = (start + end) / 2;
BuildTree(2 * node + 1, start, mid);
BuildTree(2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
public void Update(int index, int val)
{
UpdateTree(0, 0, nums.Length - 1, index, val);
}
private void UpdateTree(int node, int start, int end, int index, int val)
{
if (start == end)
{
nums[index] = val;
tree[node] = val;
}
else
{
int mid = (start + end) / 2;
if (index >= start && index <= mid)
{
UpdateTree(2 * node + 1, start, mid, index, val);
}
else
{
UpdateTree(2 * node + 2, mid + 1, end, index, val);
}
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
public int Query(int start, int end)
{
return QueryTree(0, 0, nums.Length - 1, start, end);
}
private int QueryTree(int node, int start, int end, int qStart, int qEnd)
{
if (qStart > end || qEnd < start)
{
return 0;
}
else if (qStart <= start && qEnd >= end)
{
return tree[node];
}
else
{
int mid = (start + end) / 2;
int leftSum = QueryTree(2 * node + 1, start, mid, qStart, qEnd);
int rightSum = QueryTree(2 * node + 2, mid + 1, end, qStart, qEnd);
return leftSum + rightSum;
}
}
}
```
此代码实现了线段树的构建、更新和查询功能。在构造函数中,我们创建了一个数组来存储线段树,并调用BuildTree方法来构建树。Update方法用于更新树中的一个元素,Query方法用于查询树中某个范围的元素之和。
这个实现使用了一个递归的方法来构建、更新和查询线段树。在每个节点中,我们计算左子树和右子树的总和,并将它们相加以得到节点的值。
总的来说,这个实现是比较标准的,可以用于解决各种线段树问题。