最后更新
四刷
09-Jan-2017
区间内频繁查找，更新。。
先用线段树(SegmentTree)来做，这个题几乎是把线段树的操作都用了一遍。
每个NODE只有4种可能
1）如果l-r包含了整个NODE，那么就是这个node；
2）如果l-r在整个NODE范围的外面，那么无视此node;
3）如果l-r在左边或者右边，选其中一边；
4）如果l-r同时覆盖左边右边，两边都要选。
Initiliaztion： O(n) 假如区间有N个元素，最多会有2N-1个node(not leaf)，所以建树还是O(N).
Update: O(lgN)
最多只会有4个node被我们选取，而且还是底层，否则中间应该只有2个会被选：
你找出个多于4的情况我直播吃屎。
或者把它当做balanced binary tree..查找就和树的高度有关.
Query: O(lgN) 和update一样，都是定位问题。
Space: O(N) 来存整个
public class NumArray {public class SegmentTreeNode {int start;int end;int sum;SegmentTreeNode left;SegmentTreeNode right;public SegmentTreeNode(int start, int end, int sum) {this.start = start;this.end = end;this.sum = sum;this.left = this.right = null;}}SegmentTreeNode root;public SegmentTreeNode buildTree(int start, int end, int[] nums) {if (start > end) return null;if (start == end) return new SegmentTreeNode(start, start, nums[start]);int mid = start + (end - start) / 2;SegmentTreeNode leftChild = buildTree(start, mid, nums);SegmentTreeNode rightChild = buildTree(mid + 1, end, nums);SegmentTreeNode tempRoot = new SegmentTreeNode(start, end, leftChild.sum + rightChild.sum);tempRoot.left = leftChild;tempRoot.right = rightChild;return tempRoot;}public NumArray(int[] nums) {root = buildTree(0, nums.length - 1, nums);}void update(int i, int val) {updateSegmentTree(root, i, val);}void updateSegmentTree(SegmentTreeNode root, int i, int val) {if (root == null) return;if (i < root.start || i > root.end) return;if (root.start == i && root.end == i) {root.sum = val;} else {updateSegmentTree(root.left, i, val);updateSegmentTree(root.right, i, val);root.sum = root.left.sum + root.right.sum;}}public int sumRange(int i, int j) {return sum(root, i, j);}public int sum(SegmentTreeNode root, int start, int end) {if (root == null) return 0;if (end < root.start || start > root.end) return 0;int newStart = Math.max(root.start, start);int newEnd = Math.min(root.end, end);if (root.start == newStart && root.end == newEnd) return root.sum;return sum(root.left, newStart, newEnd) + sum(root.right, newStart, newEnd);}}
然后是树状数组的做法。。一会补上。
记住这么几个：
1) fenWickTree的index是从1，开始。
2) 往右上找是 index += (index & -index);
3) 往左上找是 index -= (index & -index);
这个题是用一种 变化 的思想，即使initialization都是看做从0变化为nit的值。
需要保存2 个array，一个是fenWickTree，另一个是当前nums[]的值，用于更新的时候知道某一个element变化了多少。
Time:
init: O(NlgN)
update, query: O(lgN)
public class NumArray {int[] fenWickTree;int[] nums;public NumArray(int[] nums) {this.fenWickTree = new int[nums.length + 1];this.nums = new int[nums.length];for (int i = 0; i < nums.length; i++) {update(i, nums[i]);}}void update(int i, int val) {int diff = val - nums[i];nums[i] = val;// j is the index in fenWickTree array, so +1int j = i + 1;while (j < fenWickTree.length) {fenWickTree[j] += diff;j += (j & -j);}}public int sum(int i) {int total = 0;int j = i + 1;while (j > 0) {total += fenWickTree[j];j -= (j & -j);}return total;}public int sumRange(int i, int j) {return sum(j) - sum(i-1);}
}一刷
一开始很天真，用DP做
发现超时了。。
然后查资料发现==线段树==或者==树状数组==的应用。
我现在对那些发明这些结构的人，真是五体投地，我真心服。
先说树状数组吧
这个数据结构的原理比较复杂，我在那时没明白作者如何想出来的这个结构，只能解释下它是怎么作用的。
处理原数组index来建立一个类似于Tree的结构。
规律就是看index变成binary后 ==最右== ==不为0==的bit在哪一位。
| index | binary | right most non-zero bit |
|---|---|---|
| 1 | 0 0 0 1 | 1 |
| 2 | 0 0 1 0 | 2 |
| 3 | 0 0 1 1 | 1 |
| 4 | 0 1 0 0 | 4 |
| 5 | 0 1 0 1 | 1 |
| 6 | 0 1 1 0 | 2 |
| 7 | 0 1 1 1 | 1 |
| 8 | 0 1 0 0 | 8 |
| 9 | 1 0 0 1 | 1 |
| 10 | 1 0 1 0 | 2 |
加粗的地方是不是很像BST
纵轴是最右不为0的BIT位
横轴是INDEX
可以看出是个TREE的结构 所以新结构我们定义成一个ARRAY就可以
然后我们怎么来利用呢
ARRAY里保存的数是其所有左边节点的value+自己的VALUE
newArray[4]保存的是nums[1]+nums[2]+nums[3]+nums[4]
而newArray[3]因为没有左子树，所以保存的只有nums[3]自己
所以当nums[n]变化的时候，他所有的父节点都变化。
比如我们要求nums[0] to nums[7]的和
分成3部分
newArray[7] + newArray[6] + newArray[4]
言外之意是把它当做右边的子节点，然后找父节点，父节点自动包含父节点左边所有的值，直到找不到父节点为止。
比如7的时候，父节点是6，然后6的父节点是4.
7包含nums[7]
6包含ums[6] nums[5]
4包含nums[4] 3 2 1
4作为右节点没有父节点了。
再比如我们需要求num[4] to nums[7]， 就是4 5 6 7
newArray[7] = num[7]
newArray[6] = num[5] + num[6]
newArray[4] = num[4] + num[3] + num[2] + num[1]
这里7 6 4的顺序是从最大的7开始找左父节点找到的顺序.
最终结果就是（newArray[7] + newArray[6] + newArray[4]） - newArray[3]
那怎么找到所谓的父节点。
对于任意一个index，他的右父节点是 index + (index & -index)
我觉得这个记住比理解更便捷。。
如果它是右分支，那么他的左父节点是 index - ( index & -index)
比如途中的INDEX = 2，父节点是 2 + (2 & -2) 答案是4.
用刚才的7作为例子。
作为右节点
index = index - (index & -index)就能找到父节点
如果index < 0说明没了
作为左节点
index = index + (index & -index)就能找到父节点
如果index > newArray.length说明没父节点了
知道这些就可以有效利用了
需要注意的是，对于一个点，我们只能知道他的左父节点，或者右父借点，对于他的CHILDREN，我们无从得知，不管left child or Right child, both could be more than 1.
比较反社会的是，TREE里每个NODE的初始化，并不是比如tree[4]就寻找子节点，然后从1加4，而是只当做nums[4]从0变化到现在的num[4]，因而更新整个右边的parent nodes.
以下图为例：
实际上初始的情况是从初始化tree[1]开始，tree[1],tree[2],tree[4],tree[8]都被更新了。
再初始化tree[2],然后tree[2],tree[4],tree[8]都被更新了。
再初始化tree[3],然后tree[3]tree[4],tree[8]都被更新了。
再初始化tree[4],然后tree[4],tree[8]都被更新了。
tree[5] = > tree[5], tree[6], tree[8]被更新。
....
public class NumArray
{int[] nums;int[] tree;public NumArray(int[] nums) {this.nums = nums;this.tree = new int[nums.length+1];for(int i = 0; i < nums.length;i++){change(i+1,nums[i] - 0); //all initialized as 0 in array, so its - 0. }}// nums[i] has been changed, so we need to change every father // node related to tree[i+1].(i+1 instead of i is simply becuase we set our tree// index starting with 1 not 0)public void change(int i, int val) {while(i < tree.length){tree[i] += val;i += (i & -i);}}public void update(int i, int val){change(i+1,val - nums[i]);nums[i] = val;}// starting from node i, add all its parent nodes up.(if there is any)//public int getSum(int i){int res = 0;while( i > 0){res += tree[i];i -= (i&-i);}return res;}public int sumRange(int i, int j) {return getSum(j+1) - getSum(i);}
}INDEX对应从1开始，不是0，所以要注意。
很巧妙
初始化是n logn
查询是logn
更新是logn
很巧妙的数据结构...五体投地
