所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
具体题目
307. Range Sum Query - Mutable
题意：给出一个整数数组nums，求给出下标区间，求区间和，另外，要实现一个update函数，可以修改nums中任意下标的数字。
解：如果是不修改的，那么可以使用前缀数组和来计算，但是当数组可变的情况下，就不适用了，因为每次找区间和都要花费O(n)时间。 现在的解题思路是使用高级的数据结构，将计算区间和的时间复杂度降到O(logn)，但是更新元素的时间复杂度也上升到O(logn)。 一种结构就是线段树，线段树使用双倍的数组空间，整个数组表达二叉树结构。双倍的数组空间中，一半是原来的数组元素（这一半元素作为叶子节点，且放在双倍数组的后半部分），另一半的元素是数组的某些下标的区间和。叶子节点的父节点放什么区间和呢？答案是放入两个孩子的和，父节点的下标是叶子节点下标除2向下取整。也就是下标i的节点元素等于下标2i 和下标2i + 1两个子节点的和，这样一直到达顶部的一个dummy node。求下标区间的时候，只需要从后半段两个结点分别向上找父节点，直到找到公共父节点，那么就是区间和。更新一个结点i的时候，要从叶子结点开始向上更新所有结点，要注意的是，先要看当前叶子结点是父节点的左孩子还是右孩子，如果自己是左孩子，那么我们知道i + 1是父节点的右孩子，所以根据自己结合右孩子就可以向上更新，反之，如果自己是右孩子，那么向上更新的两个坐标是i和i-1。父节点往上更新的时候，也要看自己是其父节点的左孩子还是右孩子。 判断是左孩子还是右孩子，其实就是看是不是偶数，偶数就是左孩子。 如何求区间和(i, j)？方法是先看小下标i是左孩子且大下标j是右孩子，如果是，那么往上找公共父节点就可以了，不然的话，例如i是右孩子，那么结果要先加上自己，然后剩余结果就是算自己下一个结点（是个右孩子）与j的区间。对j也是同理，如果j是个左孩子，那么先加上j的元素，然后，计算剩余的之前的左孩子与前面的区间。 参考：https://leetcode.com/problems/range-sum-query-mutable/solution/ https://www.youtube.com/watch?v=S0Bf9jpgHmQ
另一种数据结构是树状数组Binary Indexed Tree。BIT使用单独的新数组tree数组来组建树结构，数组大小是原来数组大小+1，在0下标处存放dummy node，原数组也往右平移1。原理是新数组tree一个元素表示原数组A区间和，与线段树思想大致相同，也有更新和求区间和两种操作。区别就在于构建树的规则，操作细节的区别。 具体的，就是tree[i] = A[i - 2^k + 1] + … + A[i - 1] + A[i]，k表示i的二进制的最后连续0的个数。原理就是奇数的结尾是没有0的，而偶数的连续0的个数的2次方可以对前面的元素进行“总结”：只是2的倍数的偶数总结前面一个元素和自己，只是4的倍数的偶数可以总结倒数第三个元素到自己的元素和。 例如：tree[1] = A[1] tree[2] = A[1] + A[2] = tree[1] + A[2] tree[3] = A[3] tree[4] = A[1] + A[2] + A[3] + A[4] = tree[2] + tree[3] + A[4] tree[5] = A[5] tree[6] = A[5] + A[6] = tree[5] + A[6] tree[7] = A[7] tree[8] = A[1] + A[2] +… + A[8] = tree[4] + tree[6] + tree[7] + A[8] 注：其中A数组已经往右平移了1。 首先掌握如何快速计算2^k，如果使用右移加判断最后一位是不是0，那么时间复杂度是O(logn)的，因为期望有logn个0结尾。另外有一种技巧O(1)求解：那就是lowbit函数， x&(-x)就等于2^k，其中x要求大于0。x&(-x)就可以得出答案的原因就是-x就是把原码的最后一个1凸显出来，最后一个1之前的高位与原码完全相反，与操作之后必然变为0，而1之后的低位全是0。 接下来问题之一是，如何更新：更新原数组A[i]会影响tree数组多个元素，假设1被修改了，那么受影响的tree结点是1,2,4,8。画出tree的树结构仔细观察，发现影响的元素从tree[i]开始，沿着父节点直到tree树的根节点，其他的结点不受影响，也就是说，找出i结点的父节点这一操作很重要。发现父节点下标y == i + 2^k。原理就是， 如果i是奇数，那么他的父节点就是下一个元素，而i只是2的倍数时候，找到下一个只是2的倍数，如果是4的倍数，那么找到下一个4的倍数。 问题之二是，如何构建tree树：只需要对每个位置，使用原数组的相应位置的值进行更新就可以了。 问题之三是，如何求区间和：答案是先求出前缀和，后使用前缀和相减得出区间和。求前缀和preSum[i]: preSum[i] = A[1] + A[2] + … + A[i] = A[1] + A[2] + … + A[i - 2^k + 1] + … + A[i] = preSum[i - 2^k] + tree[i] = preSum[i - lowbit(i)] + tree[i] 说白了，使用tree数组求preSum的过程是一个递归的过程，当i == 0的时候，返回0结束递归。要求preSum[i]，那么先求 preSum[i - lowbit(i)]，要注意的是i - lowbit(i)并不是 i + lowbit(i)的逆过程，也就是不是找子节点，例如8 - lowbit(8) == 0。但是下降仍然是沿着树高下降的，因此复杂度是O(logn)。使用迭代取代递归也可以，消除了递归的开销。 参考：https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/ https://www.jiuzhang.com/tutorial/binary-indexed-tree/295
308. Range Sum Query 2D- Mutable
题意：此题是带更新操作的二维矩阵。
解：还是使用bit，此时使用tree[i][j]表示一个以(i,j)为右下角结尾，以(i - 2^k + 1, j - 2^k + 1)左上角开始的子二维矩阵总和。
