欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

JAVA程序设计:区域和检索 - 数组可修改(LeetCode:307)

程序员文章站 2024-03-05 16:57:31
...

给定一个整数数组  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];
    }
}