CShap 实现Fenwick tree 源代码

以下是C#实现Fenwick树的示例代码：

public class FenwickTree
{
    private int[] tree;

    public FenwickTree(int size)
    {
        tree = new int[size];
    }

    public void Update(int index, int value)
    {
        while (index < tree.Length)
        {
            tree[index] += value;
            index |= (index + 1);
        }
    }

    public int Query(int index)
    {
        int sum = 0;
        while (index >= 0)
        {
            sum += tree[index];
            index = (index & (index + 1)) - 1;
        }
        return sum;
    }
}

该代码实现了Fenwick树的两个基本操作：更新和查询。Update（index，value）将tree数组中索引为index的元素增加value，并将index移动到下一个索引，以便更新其父节点。Query（index）将返回索引为0到index的元素的总和。

要使用Fenwick树，您可以创建一个新的FenwickTree对象并使用其Update和Query方法。例如，以下代码将创建一个Fenwick树，将其所有元素设置为0，然后将前5个元素分别设置为1、2、3、4和5：

FenwickTree ft = new FenwickTree(10);
for (int i = 0; i < 10; i++)
{
    ft.Update(i, 0);
}
for (int i = 0; i < 5; i++)
{
    ft.Update(i, i + 1);
}

现在，您可以使用Query方法来查询索引为0到5的元素的总和：

int sum = ft.Query(5);
Console.WriteLine(sum); // 输出 "15"