Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8
Note:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
本题主要考查的是两种数据结构，一种是二分索引树，另一种是线段树。
先说线段树，用于解决连续区间的动态查询问题，实现起来不是很复杂，代码如下：
1 public class NumArray { 2 class SegmentTreeNode{ 3 int start; 4 int end; 5 int sum; 6 SegmentTreeNode left,right; 7 public SegmentTreeNode(int start,int end){ 8 this.start = start; 9 this.end = end; 10 this.left = null; 11 this.right = null; 12 this.sum = 0; 13 } 14 } 15 SegmentTreeNode root = null; 16 public NumArray(int[] nums) { 17 root=buildtree(nums,0,nums.length-1); 18 } 19 public SegmentTreeNode buildtree(int[] nums,int start,int end){ 20 if(start>end){ 21 return null; 22 }else{ 23 SegmentTreeNode node = new SegmentTreeNode(start,end); 24 if(start==end){ 25 node.sum = nums[start]; 26 }else{ 27 int mid = start+(end-start)/2; 28 node.left = buildtree(nums,start,mid); 29 node.right = buildtree(nums,mid+1,end); 30 node.sum = node.left.sum+node.right.sum; 31 } 32 return node; 33 } 34 } 35 36 public void update(int i, int val) { 37 update(root,i,val); 38 } 39 public void update(SegmentTreeNode root,int pos,int val){ 40 if(root.start==root.end){ 41 root.sum = val; 42 }else{ 43 int mid = root.start+(root.end-root.start)/2; 44 if(pos<=mid){ 45 update(root.left,pos,val); 46 }else{ 47 update(root.right,pos,val); 48 } 49 root.sum = root.left.sum+root.right.sum; 50 } 51 } 52 public int sumRange(int i, int j) { 53 return sumRange(root,i,j); 54 } 55 public int sumRange(SegmentTreeNode root,int start,int end){ 56 if(root.start==start&&root.end==end) return root.sum; 57 else{ 58 int mid = root.start+(root.end-root.start)/2; 59 if(start>mid){ 60 return sumRange(root.right,start,end); 61 }else if(end<=mid){ 62 return sumRange(root.left,start,end); 63 }else{ 64 return sumRange(root.left,start,mid)+sumRange(root.right,mid+1,end); 65 } 66 } 67 } 68 } 69 70 /** 71 * Your NumArray object will be instantiated and called as such: 72 * NumArray obj = new NumArray(nums); 73 * obj.update(i,val); 74 * int param_2 = obj.sumRange(i,j); 75 */
下面是二分索引树，该树要注意一点，就是下标从1开始的，代码如下：
1 public class NumArray { 2 int[] BIT; 3 int[] nums; 4 int len; 5 public NumArray(int[] nums) { 6 len = nums.length; 7 BIT = new int[len+1]; 8 this.nums = nums; 9 for(int i=0;i<len;i++){ 10 init(i,nums[i]); 11 } 12 } 13 public void init(int i,int val){ 14 i++; 15 while(i<=len){ 16 BIT[i] += val; 17 i+=(i&-i); 18 } 19 } 20 21 public void update(int i, int val) { 22 int diff = val-nums[i]; 23 nums[i] = val; 24 init(i,diff); 25 } 26 public int getSum(int i){ 27 int sum = 0; 28 i++; 29 while(i>0){ 30 sum += BIT[i]; 31 i-=(i&-i); 32 } 33 return sum; 34 } 35 36 public int sumRange(int i, int j) { 37 return getSum(j)-getSum(i-1); 38 } 39 } 40 41 /** 42 * Your NumArray object will be instantiated and called as such: 43 * NumArray obj = new NumArray(nums); 44 * obj.update(i,val); 45 * int param_2 = obj.sumRange(i,j); 46 */