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];
}
}
推荐阅读
-
JAVA程序设计:区域和检索 - 数组可修改(LeetCode:307)
-
C# 实现LeetCode 307. 区域和检索 - 数组可修改
-
leetcode 307. 区域和检索 - 数组可修改 树状数组
-
Leetcode 307. 区域和检索 - 数组可修改
-
Leetcode 307. 区域和检索 - 数组可修改
-
LeetCode-307. 区域和检索 - 数组可修改
-
LeetCode 307. 区域和检索 - 数组可修改
-
Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable (线段树Segment Tree)-超详细Python
-
Leetcode 区域和检索 - 数组可修改
-
Java实现 LeetCode 307 区域和检索 - 数组可修改