## 树状数组总结
最容易懂的工具: [**点这里**](https://visualgo.net/en/fenwicktree)。
一张图概括:
具体演示可以看上面的链接。
[**LeetCode - 307. Range Sum Query - Mutable**](https://leetcode.com/problems/range-sum-query-mutable/)例题:
题目:
树状数组代码:
```java
class NumArray {
private int[] sums;// 树状数组中求和的数组
private int[] data;//真实存放数据的数组
private int n;
private int lowbit(int x) {return x & (-x);}
private int query(int i){
int s = 0;
while(i > 0){//树状数组中索引是1~n
s += sums[i];
i -= lowbit(i);
}
return s;
}
// fenWick update
private void renewal(int i, int delta){// delta是增量，不是新值
while(i <= n){//树状数组中索引是1~n
sums[i] += delta;
i += lowbit(i);
}
}
public NumArray(int[] nums) {
n = nums.length;
sums = new int[n+1];
data = new int[n];
for(int i = 0; i < n; i++) {
data[i] = nums[i];
renewal(i+1, nums[i]);
}
}
public void update(int i, int val)
