JAVA程序设计：区域和检索 - 数组可修改（LeetCode：307）

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:

数组仅可以在 update 函数下进行修改。
你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

思路：这题解法很多：暴力、前缀和、树状数组、线段树等都是可以的，本题我采用了方法相对较优的线段树解决这道题，也算是回顾了一下线段树了。

class NumArray {

	int[] sum;
	int length;
    public NumArray(int[] nums) {
    	length=nums.length;
    	if(length==0) return;
        sum=new int[nums.length<<2];
        findsum(1,1,length,nums);
    }
    
    public void update(int i, int val) {
        Update(1,1,length,i+1,val);
    }
    
    public int sumRange(int i, int j) {
        return sum(1,1,length,i+1,j+1);
    }
    
    public int sum(int id,int l,int r,int ls,int rs)
    {
    	if(l>r) return 0;
    	if(ls<=l && rs>=r)
    		return sum[id];
    	int mid=(l+r)/2,ret=0;
    	if(ls<=mid)
    		ret+=sum(id*2,l,mid,ls,rs);
    	if(rs>mid)
    		ret+=sum(id*2+1,mid+1,r,ls,rs);
    	return ret;
    }
    
    public void Update(int id,int l,int r,int i,int val)
    {
    	if(l==r) 
    	{
    		sum[id]=val;
    		return;
    	}
    	int mid=(l+r)/2;
    	if(i<=mid)
    		Update(id*2,l,mid,i,val);
    	else
    		Update(id*2+1,mid+1,r,i,val);
    	sum[id]=sum[id*2]+sum[id*2+1];
    }
    
    public void findsum(int id,int l,int r,int[] nums)
    {
    	if(l==r) 
    	{
    		sum[id]=nums[l-1];
    		return;
    	}
    	int mid=(l+r)/2;
    	findsum(id*2,l,mid,nums);
    	findsum(id*2+1,mid+1,r,nums);
    	sum[id]=sum[id*2]+sum[id*2+1];
    }
}