所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
线段树： https://www.youtube.com/watch?v=e_bK-dgPvfM&t=932s&ab_channel=%E9%BB%84%E6%B5%A9%E6%9D%B0
线段树看起来的样子：区间{1, 16}的线段树，root节点（第0层）是{1, 16}，然后第一层是{1, 8}， {9，16}；
第二层是{1, 4},{5, 8},{9, 12}, {13, 15}，依次类推。
所以，一开始这个区间是确定的，然后就可以对这个区间构建线段树，例如
根据一个数组（A[0]， A[1], A[2], …A[N - 1]）构建起来的线段树，它的
最大作用是可以O(logN)的时间找出任意给定的一个下标区间的函数f(i, j)，例如：区间和，区间内每个元素的AND，区间内的最大（小）值等。
一般来说，计算f(i, j)，要把每个[i, j]区间的元素都遍历一遍，加入计算，总体时间复杂度是O（N）的。
但是为什么线段树是可以做到O(logN)时间呢？原因就是，[i, j]不是每个元素都遍历的，而是其中的区间碎片已经被计算过了。
也就是说，先花N的时间，计算出部分区间，组成线段树，到真正计算某个区间的时候，再花O(logN)时间找到。
举个例子，要计算[1,4]，实际上，可以递归的看这个问题，就是按中间值拆分为计算[1,2]和[3,4]这两个问题，而这两个问题继续递归，最后变成[1],[2],[3],[4]这四个已经解决了的最基本问题。
实际上，线段树先把这些碎片的问题计算好：以N = 16为例，且假设下标从1开始，那么第一层：[1, 8], [9, 16]， 第二层[1, 4],[5, 8],[9, 12], [13, 15]，
依次类推，叶子节点就是区间里面只有一个元素的情况。
我们知道，这样的节点数量是N + N / 2 + N / 4 + … + 1 = 2N个的，也就是先花费O（N）的时间计算好这些区间，并组织成树的结构。
好处：支持数组的随时更新，找出任意一个区间的结果仍然是O(logN)。
再来看更新这个线段树的情况： 更新的成本就是从叶子影响到根节点（也可以从根节点到叶子节点），也就是经过树高的路径，耗时O(logN)来更新。
编码：有三个主要函数：build，update，get(L,R)。 build的主要思路是递归：要构建区间[start，end]，那么就先要构建区间[start，mid]和[mid + 1，end]。递归出口就是start == end的时候，直接当前节点的值作为区间的答案。
update的主要思路也是递归：要更新一个下标i，那么从[start，end]开始找，如果i落在start和end之间，说明这个区间需要更新，但也是先更新区间[start，mid]和[mid + 1，end]， 然后根据两个区间的更新结果更新自己。递归的出口是叶子（start == end的时候），直接更新当前区间为更新值，同时也更新这个数组本身的值。
get(L,R)的主要思路也是递归：找区间[L, R]的值，那么先看和[start，end]的关系，其中每一层都是相同[L, R]，但是是不同[start，end]， 有三种：
- [L, R]完全落在了[start，end]的外面，也就是左侧或者右侧
那么应该直接返回默认值(就是不会干扰上一层计算的值)；
- [L, R]完全包含当前[start，end]
理解：这就好像是投影，想象把[L, R]从线段树的上面往下投，那么，其实一个线段树节点上的区间一旦落入[L, R]的阴影里面，那么其实就是可以直接拿出来复用的。
不必在往下计算，所以，返回当前[start，end]的结果给上一层使用。
- 如果[L, R]与[start，end]有重叠
还是按投影理解，说明[start，end]没有被阴影完全覆盖，不足够解决问题，必须向下进行拆解，递归处理。 拆的时候，也就是交给[start，end]两个下面的节点去处理。
线段树用数组实现：使用node_index，左子树的root是node_index * 2，右子树的root是node_index * 2 + 1；
实现参考3171题。
具体题目
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)左上角开始的子二维矩阵总和。
