# 树状数组

解决的问题

树状数组可以同时实现 O(logn) 时间复杂度：

获取 arr[0]~arr[i] 的和
对 arr[i] 进行修改。

这两个要素，如果只需要实现单独的要求，甚至可以做到 O(1) ，但是同时实现的话，不用树状数组，就只能是一个 O(n) ，另一个 O(1) 。当 n 比较大的时候，效率就比较低。

# 构建

假设目标数组是 arr ，要构建 arr 的树状数组 tr ，这里要提示的是，arr 最理想的是向右移动一格，不使用 i==0 ：

下面提到的 arr[i] 都是变换后的

定义 tr[i] = arr[i-2^k+1] + .. + arr[i-1] + arr[i] ， k 是 i 二进制末尾 0 的个数。
tr 的下标从 1 开始。
2^k 可以通过 i & (-i) 获得，这个数的本质就是 tr[i] 管理的节点个数。

假设 arr 有 9 个元素，变换后就是 arr[1]~arr[9] ， arr[i] 就是第 i 个数，那么通过上面的变换就是：

	tr[1] = arr[1] # 1 + 1&(-1) + 1 = 1
	tr[2] = arr[1] + arr[2]
	tr[3] = arr[3]
	tr[4] = arr[1] + arr[2] + arr[3] + arr[4] = tr[2] + tr[3] + arr[4]
	tr[5] = arr[5]
	tr[6] = arr[5] + arr[6]
	tr[7] = arr[7]
	tr[8] = arr[1] + ... + arr[8] = tr[4] + tr[6] + tr[7] + arr[8]
	tr[9] = arr[9]

就得到树状数组：

我们怎么去获得这个 tr 数组呢？我们假设已经有了对 arr 数组修改元素的操作 add() ，这就需要维护 tr 数组，我们可以将 arr 所有元素看作 0，然后依次将现有数据加进去。

	for(int i = 0;i < arr.length;i++) {
	add(i+1,arr[i]);
	}

# 修改

修改一个节点 ( arr[i] 加了 x )，就必须修改所有祖先节点，最多有 log (n) 个节点：

i >= n ，算法结束。
tr[i] = tr[i] + x;i = i + (i&(-i)); ，回到第一步。

代码：

	int lowbit(int x) {
	return x & -x;
	}
	void add(int x, int u) {
	for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
	}

这里有个问题，就是 add 不能传入 0，不然循环就无法结束。也就是说， tr[0] 是不能用的，需要用 tr[1] 来管理 arr[0] 。为了不那么绕，我们在脑海中将 arr 向右移动一格即可，即 arr[i] 对应 tr[i+1] ，通过 add(i+1,x) 来屏蔽差异。

解释代码：

主要看上面的图，假设 A[1] 加了 1，那么管理 A[1] 树状数组都需要改变：

C[1]，C[2]，C[4]，C[8] 都管理着 A[1] ，所以只需要改变这几个的值。
同时 A[i] 首先是被 C[i] 管理着，所以我们可以从 C[i] 向上寻找。
从 C[1] 向上找到 C[8] ，其实就是 i+lowbit(i) 的操作。

i+lowbit(i) 就是加上 i 最后一位 1 的值。

# 查询

想要获取 arr[i] 的前面的和：

ans=0； 。
i<=0 ，返回 ans ；否则 ans += tr[i] 。
i -= lowbit(i) ，回到第二步。

还是看上图，比如求 arr[1]+arr[6] ，就是找到 tr[6] ，然后再进入循环， 6-lowbit(6) 就是 4。

	public int query(int i) {
	int ans = 0
	for(;i > 0;i -= lowbi(i)) {
	ans += tr[i];
	}
	return ans;
	}

# 完整代码

	public class Solution {
	int[] trx;
	int n;

	private int lowbit(int i) {
	return i & (-i);
	}

	//add 操作不处理 arr 数组的修改，交给其他方法处理
	private void add(int x, int u) {
	for(int i = x; i <= n; i += lowbit(i)) {
	tr[i] += u;
	}
	}

	private int query(int x) {
	int ans;
	for(int i = x;i > 0;i -= lowbit(i)) {
	ans += tr[i];
	}
	return ans;
	}

	public void process(int[] arr) {
	n = arr.length;
	trx = new int[n+10];// 其实 n+1 就够了

	// 初始化树状数组
	for(int i = 0;i < n;i++) {
	add(i+1, arr[i]);
	}
	// 一系列操作
	}
	}

# 参考

https://www.cnblogs.com/Lehman-Share/p/8004983.html
宫水三叶 - LC307

数据结构与算法