返回信息流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
这题用segment tree 的标准实现方式超时了...可能是leetcode更新了test case...怎么优化呢
以下是代码，按照voting最高的那个solution实现的，但现在TLE了，求大神指导
public class NumArray {
SegmentNode root;
public NumArray(int[] nums) {
root = buildTree(nums,0,nums.length-1);
}
SegmentNode buildTree(int[] nums, int start, int end){
if(end>start) return null;
SegmentNode node = new SegmentNode(start,end);
int mid = (start+end)/2;
if(end==start)
node.sum = nums[start];
else{
node.left = buildTree(nums,start,mid);
node.right = buildTree(nums,mid+1,end);
node.sum = node.left.sum + node.right.sum;
}
return node;
}
void update(int i, int val) {
updateNode(root,i,val);
}
void updateNode(SegmentNode root, int i, int val){
if(root.end==i&&root.start==i){
root.sum = val;
return;
}
int mid = (root.start+root.end)/2;
if(i<=mid){
updateNode(root.left,i,val);
} else{
updateNode(root.right,i,val);
}
root.sum = root.left.sum+root.right.sum;
}
public int sumRange(int i, int j) {
return query(root,i,j);
}
int query(SegmentNode root, int start, int end){
if(root.start == start&&root.end == end){
return root.sum;
}else{
int mid = (root.start+root.end)/2;
if(start<=mid && end>mid){
return query(root.left,start,mid) + query(root.right,mid+1,end);
} else if(end<=mid){
return query(root.left,start,end);
} else{
return query(root.right,start,end);
}
}
}
}
class SegmentNode{
int start;
int end;
int sum;
SegmentNode left;
SegmentNode right;
SegmentNode(int start,int end){
this.start = start;
this.end = end;
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90805同步于 2016/8/15
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[leetcode]307. Range Sum Query - Mutable
chihiro2B
2016/8/15镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
`buildTree`方法的第一行错了
```
if(end>start) return null;
```
改成下面或直接去掉
```
if(end < start) return null;
```
【 在 chihiro2B 的大作中提到: 】
: [md]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:
: ...................
【 在 deadend 的大作中提到: 】
: [md]
: `buildTree`方法的第一行错了
: ```
: ...................
慧眼如炬！
但tle的问题不是这个。。leetcode有bug了。。
构造方法也要改。。
```
public NumArray(int[] nums) {
if (nums == null || nums.length == 0)
return;
root = buildTree(nums, 0, nums.length - 1);
}
```
重复提交代码时，有时貌似会提交之前缓存的代码，好像是有这样的问题
【 在 chihiro2B 的大作中提到: 】
:
: 慧眼如炬！
: 但tle的问题不是这个。。leetcode有bug了。。
【 在 deadend 的大作中提到: 】
: [md]
: 构造方法也要改。。
: ```
: ...................
请问构造方法哪里有错呢，我AC了( o? ω o? )y
哦哦，那就没问题啦，如果删掉下面这行判断，需要修改构造函数
```
if(end < start) return null;
```
【 在 chihiro2B 的大作中提到: 】
:
: 请问构造方法哪里有错呢，我AC了( o? ω o? )y