# Binary Indexed Tree

![](/files/-M63nTEKIgVrGftxuxY0)

定义`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];
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/binary-indexed-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.