本文主要是介绍Range Sum Query - Mutable,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
先补知识:
Segment Tree 线段树
Binary Indexed Tree 树状数组
明天再补充
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.
题意很好理解。返回部分和 可以修改某个数同时返回的部分和会更新
代码参照 YRB 总结的很好,而且是用java写的,一个题会用好几种方法做 赞 最近好多都是看它的博客
http://www.cnblogs.com/yrbbest/p/5056739.html
public class NumArray {private class SegmentTreeNode{public int start;public int end;public int sum;public SegmentTreeNode left,right;public SegmentTreeNode(int start,int end){this.start=start;this.end=end;this.sum=0;}}private SegmentTreeNode root;public NumArray(int[] nums) {this.root=buildTree(nums,0,nums.length-1);}public void update(int i, int val) {update(root,i,val);}public void update(SegmentTreeNode node,int position, int val){if(node.start==position&&node.end==position){node.sum=val;return ;}int mid=node.start+(node.end-node.start)/2;if(position<=mid){update(node.left,position,val);}else{update(node.right,position,val);}node.sum=node.left.sum+node.right.sum;}public int sumRange(int i, int j) {return sumRange(root,i,j);}private int sumRange(SegmentTreeNode node,int lo,int hi){if(node.start==lo&&node.end==hi)return node.sum;int mid=node.start+(node.end-node.start)/2;if(hi<=mid){return sumRange(node.left,lo,hi);}else if(lo>mid){return sumRange(node.right,lo,hi);}else {return sumRange(node.left,lo,mid)+sumRange(node.right,mid+1,hi);}}private SegmentTreeNode buildTree(int []nums,int lo,int hi){if(lo>hi){return null;} else{SegmentTreeNode node=new SegmentTreeNode(lo,hi);if(lo==hi){node.sum=nums[lo];}else{int mid=lo+(hi-lo)/2;node.left=buildTree(nums,lo,mid);node.right=buildTree(nums,mid+1,hi);node.sum=node.left.sum+node.right.sum;}return node;}}
}
这篇关于Range Sum Query - Mutable的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!