1 简介

让 f 是某个 group作（具有恒等元素和逆元素的集合的二进制关联函数）和 A 是长度为 N。

表示 f 美元的中缀表示法为 * ;
那是 f（x，y） = x*y 对于任意整数 x，y. （由于这是结合的，我们将省略括号以执行 f 当使用中缀表示法时。

Fenwick 树是一种数据结构，它：

计算 function 的值 ，f在给定范围内 [l， r]（即 A_l * A_{l+1} * \dots * A_r） 在 O（\log N）$时间

更新 A在 O（\log N）$时间
需要 O(N)memory 所需的内存量相同 A
易于使用和编码，尤其是在多维数组的情况下

Fenwick 树最常见的应用是计算范围的总和。 例如，使用整数集的加法作为组运算，即 
f（x，y） = x + y：二进制运算，

* 是 + 在本例中，因此

		A_l * A_{l+1} * ... * A_r = A_l + A_{l+1} + \dots + A_{r}.

Fenwick 树也称为二进制索引树 （BIT）。 它首次在一篇题为“累积频率表的新数据结构”的论文（Peter M. Fenwick，1994 年）中进行了描述。

• 简单示例

为简单起见，我们将假设该函数 f 定义为 f（x，y） = x + y在整数上。

假设我们得到一个整数数组， A[0 … N-1]. （请注意，我们使用的是从零开始的索引。
Fenwick 树只是一个数组， T[0 … N-1]，其中每个元素等于 A 在某个范围内， [g（i）， i]:

T_i = sum_{j = g（i）}^{i}{A_j}

g 是满足  0 <= g（i） <= i.
我们将在接下来的几段中定义 g 。

数据结构被称为树，因为它以树的形式很好地表示了它，尽管我们不需要用节点和边对实际的树进行建模。
我们只需要维护数组 T 处理所有查询。

注意：此处介绍的 Fenwick 树使用从零开始的索引。 许多人使用从 1 开始的索引的 Fenwick 树版本。
因此，您还可以在 implementation 部分找到使用从 1 开始的索引的替代实现。
两个版本在时间和内存复杂性方面是等效的。

现在我们可以为上面提到的两个作编写一些伪代码。 下面，我们得到 的元素之和

下图显示了 Fenwick 树作为 tree 的可能解释。 树的节点显示它们覆盖的范围

3 在一维数组中求和

我们介绍了 Fenwick 树的实现，用于 sum 查询和单个更新。

普通的 Fenwick 树只能回答 
[0， r]使用 ，但是我们也可以回答sum(int r) [l， r]通过计算两个和。 
[0， r]和 [0， l-1]并减去它们。 这是在方法中处理的。sum(int l, int r)

此外，此实现支持两个构造函数。 您可以创建用零初始化的 Fenwick 树，也可以将现有数组转换为 Fenwick 形式

		 struct FenwickTree {
      vector<int> bit;  // binary indexed tree
      int n;

      FenwickTree(int n) {
          this->n = n;
          bit.assign(n, 0);
      }

      FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
          for (size_t i = 0; i < a.size(); i++)
              add(i, a[i]);
      }

      int sum(int r) {
          int ret = 0;
          for (; r >= 0; r = (r & (r + 1)) - 1)
              ret += bit[r];
          return ret;
      }

      int sum(int l, int r) {
          return sum(r) - sum(l - 1);
      }

      void add(int idx, int delta) {
          for (; idx < n; idx = idx | (idx + 1))
              bit[idx] += delta;
      }
  };

4 在FWK树种新增修改与求和的操作

芬威克用于解决我们在固定大小上有以下类型的多个作的问题。

前缀运算 （Sum， Product， XOR， OR， etc）.请注意，range作也可以使用 prefix 来解决。例如，从索引 L 到 R 的范围 sum 是前缀 sum till R（包括减去前缀 sum til L-1）。

更新数组项
两个作的时间复杂度都是 O（Log n）。请注意，我们需要 O（n Log n） 预处理时间和 O（n） 辅助空间。

  type FenwickTree struct {
      tree []int
  }

  func NewFenwickTree(n int) *FenwickTree {
      return &FenwickTree{make([]int, n+1)}
  }

  func (ft *FenwickTree) Update(index, delta int) {
      for i := index + 1; i < len(ft.tree); i += i & -i {
          ft.tree[i] += delta
      }
  }

  func (ft *FenwickTree) Edit(index, delta int) {
      for i := index + 1; i < len(ft.tree); i += i & -i {
          ft.tree[i] = delta
      }
  }

  func (ft *FenwickTree) Query(index int) int {
      sum := 0
      for i := index + 1; i > 0; i -= i & -i {
          j := i
          fmt.Printf("sun & j:%v\n", j&-j)
          j -= j & -j
          fmt.Printf("sun index j:%v\n", j)
          sum += ft.tree[i]
      }
      return sum
  }

  func main() {
      ft := NewFenwickTree(5)
      fmt.Printf("init ft:%#v \n", ft)
      // 示例用法：更新第3个元素的值为2
      ft.Update(2, 2)
      fmt.Printf("update 2 2 ft:%#v \n", ft)

      // 示例用法：更新第4个元素的值 +3
      ft.Update(3, 3)
      fmt.Printf("update 3 3 ft:%#v \n", ft)

      // 示例用法：查询前4个元素的和
      sum := ft.Query(3)
      fmt.Println("前4个元素的和:", sum) // 输出: 5

      // 示例用法：更新第4个元素的值 = 3
      ft.Edit(3, 3)
      fmt.Printf("edit 3 3 ft:%#v \n", ft)

      // 示例用法：查询第4个元素的和
      sum2 := ft.Query(3)
      fmt.Println("前4个元素的和:", sum2) // 输出: 5

      var k int = 0
      for k = 0; k < 10; k++ {

          fmt.Printf("k of: %v  &k: %v, binary:%b\n", k, k&-k, k&-k)
          fmt.Printf("k of: %v ^k: %v, binary:%b\n", k, k^-k, k^-k)
          fmt.Printf("k of: %v |k: %v, binary:%b\n", k, k|-k, k|-k)
          fmt.Printf("k of: %v <<k: %v, binary:%b\n", k, k<<1, k<<1)
          fmt.Printf("k of: %v >>k: %v, binary:%b\n", k, k>>1, k>>1)
          ks := -k
          fmt.Printf("k of: %v  binary:%b. binary -k:%b\n", k, k, ks)
          fmt.Printf("%b\n", *(*[8]byte)(unsafe.Pointer(&ks)))
      }
  }

5 小结

Fenwick 树可以支持以下范围作：

  点更新和范围查询
  范围更新和点查询
  Range Update 和 Range Query

1. 点更新和范围查询

这只是上面解释的普通 Fenwick 树。

2. 范围更新和点查询

使用简单的技巧，我们还可以进行反向作：增加范围并查询单个值。

让 Fenwick 树初始化为零。
假设我们想由 x 要增加 [l， r]. 我们对 Fenwick 树进行两个点更新作，它们是 和 add(l, x)add(r+1, -x)

如果我们想获取A[i]，我们只需要使用普通 range sum 方法获取前缀 sum。
要了解为什么会这样，我们可以再次关注前面的 increment作。
如果 i < l，则这两个 update作对查询没有影响，我们得到 sum 0. 如果 i in [l， r]，那么我们得到答案

x 因为第一次更新作。 如果 i > r，则第二个 update作将取消第一个 update作的效果。