> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/binary-indexed-tree.md).

# Binary Indexed Tree

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F40201cd9ae33bedcfd2adac5805c3dc40d181576.png?generation=1588144784979463\&alt=media)

定义`C[i]`的值为它的所有叶子结点的权值的总和.

`C[i]`的表达式:

`C[i]=A[i]+A[i-1]+....+A[i-2^k+1]`

**k代表i的二进制的最后连续0的个数。**

**C\[i]还有一种更加普适的定义，它表示的其实是一段原数组A的连续区间和。区间的左端点为i - 2^k + 1，右端点为i。**

```
将C[]数组的结点序号转化为二进制。
1=(001) C[1]=A[1];
2=(010) C[2]=A[1]+A[2];
3=(011) C[3]=A[3];
4=(100) C[4]=A[1]+A[2]+A[3]+A[4];
5=(101) C[5]=A[5];
6=(110) C[6]=A[5]+A[6];
7=(111) C[7]=A[7];
8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
```