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
public class NumArray {
private SegmentTreeNode root = null;
private int size = 0;
public NumArray(int[] nums) {
root = buildInSegmentTree(nums, 0, nums.length - 1);
size = nums.length;
}
void update(int i, int val) {
if(i<0 || i>=size) return;
updateInSegmentTree(root, i, val);
}
public int sumRange(int i, int j) {
if(i>j || i<0 || j>=size) return -1;
return querySum(root, i, j);
}
class SegmentTreeNode{
int lc = 0, rc = 0, sum = 0;
SegmentTreeNode left = null, right = null;
SegmentTreeNode(int l, int r, int val) {
lc = l; rc = r; sum = val;
}
}
public SegmentTreeNode buildInSegmentTree(int []nums, int l, int r) {
if(l > r) return null;
if(l == r) {
SegmentTreeNode leaf = new SegmentTreeNode(l, r, nums[l]);
return leaf;
}
SegmentTreeNode root = new SegmentTreeNode(l, r, 0);
int mid = (l + r) >> 1;
root.left = buildInSegmentTree(nums, l, mid);
root.right = buildInSegmentTree(nums, mid+1, r);
root.sum = root.left.sum + root.right.sum;
return root;
}
public void updateInSegmentTree(SegmentTreeNode root, int i, int val) {
if(root.lc == root.rc && root.lc == i) {
root.sum = val;
return;
}
int mid = (root.lc + root.rc) >> 1;
if(i >= root.lc && i <= mid) updateInSegmentTree(root.left, i, val);
else updateInSegmentTree(root.right, i, val);
root.sum = root.left.sum + root.right.sum;
}
public int querySum(SegmentTreeNode root, int i, int j) {
if(root.lc == i && root.rc == j) return root.sum;
int mid = (root.lc + root.rc) >> 1;
if(i <= mid && j <= mid) return querySum(root.left, i, j);
else if(i > mid && j > mid) return querySum(root.right, i, j);
else return querySum(root.left, i, mid) + querySum(root.right, mid+1, j);
}
}
// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);
下面附上java版segmentTree模板代码（共有两个文件：一个是SegmentTreeNode.java，另一个是SegmentTree.java。）
package cc150;
public class SegmentTreeNode {
public int lc, rc, sum, add;
SegmentTreeNode left, right;
public SegmentTreeNode() {
this.lc = 0; this.rc = 0; this.sum = 0; this.add = 0;
this.left = null; this.right = null;
}
public SegmentTreeNode(int l, int r, int val) {
this.lc = l; this.rc = r; this.sum = val; this.add = 0;
this.left = null; this.right = null;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
SegmentTreeNode.java
package cc150;
public class SegmentTree {
public SegmentTreeNode root = null;
int lower_bound, upper_bound;
public SegmentTree() {
this.root = null;
this.lower_bound = 0; this.upper_bound = 0;
}
public SegmentTree(int l, int r, int []nums) {
//@ SegmentTreeNode(left_idx, right_idx, sum).
this.root = new SegmentTreeNode(l, r, 0);
this.lower_bound = l; this.upper_bound = r;
buildSegmentTree(l, r, nums, root);
}
public void buildSegmentTree(int l, int r, int []nums, SegmentTreeNode s) {
SegmentTreeNode sroot = s;
if(l > r) return;
if(l == r) {
sroot.sum = nums[l];
return;
}
int mid = (l + r) / 2;
sroot.left = new SegmentTreeNode(l, mid, 0);
buildSegmentTree(l, mid, nums, sroot.left);
sroot.right = new SegmentTreeNode(mid+1, r, 0);
buildSegmentTree(mid+1, r, nums, sroot.right);
sroot.sum = sroot.left.sum + sroot.right.sum;
}
public void updateByPoint(SegmentTreeNode sroot, int idx, int val) {
if(idx == sroot.lc && sroot.lc == sroot.rc) {
sroot.sum = val;
return;
}
int mid = (sroot.lc + sroot.rc) / 2;
if(idx <= mid) updateByPoint(sroot.left, idx, val);
else updateByPoint(sroot.right, idx, val);
sroot.sum = sroot.left.sum + sroot.right.sum;
}
public void updateBySegment(SegmentTreeNode sroot, int l, int r, int val) {
if(l == sroot.lc && r == sroot.rc) {
sroot.add += val;
sroot.sum += val * (r - l + 1);
return;
}
if(sroot.lc == sroot.rc) return;
int len = sroot.rc - sroot.lc + 1;
if(sroot.add > 0) {
sroot.left.add += sroot.add;
sroot.right.add += sroot.add;
sroot.left.sum += sroot.add * (len - (len/2));
sroot.right.sum += sroot.add * (len/2);
sroot.add = 0;
}
int mid = sroot.lc + (sroot.rc - sroot.lc)/2;
if(r <= mid) updateBySegment(sroot.left, l, r, val);
else if(l > mid) updateBySegment(sroot.right, l, r, val);
else {
updateBySegment(sroot.left, l, mid, val);
updateBySegment(sroot.right, mid+1, r, val);
}
sroot.sum = sroot.left.sum + sroot.right.sum;
}
static int querySum(SegmentTreeNode sroot, int i, int j) {
if(i > j) {
System.out.println("Invalid Query!");
return -1;
}
if(i<sroot.lc || j>sroot.rc) return querySum(sroot, sroot.lc, sroot.rc);
if(sroot.lc == i && sroot.rc == j) return sroot.sum;/*
int len = sroot.rc - sroot.lc + 1;
if(sroot.add > 0) {
sroot.left.add += sroot.add;
sroot.right.add += sroot.add;
sroot.left.sum += sroot.add * (len - len/2);
sroot.right.sum += sroot.add * (len/2);
sroot.add = 0;
}
*/
int mid = (sroot.lc + sroot.rc) / 2;
if(j <= mid) return querySum(sroot.left, i, j);
else if(i > mid) return querySum(sroot.right, i, j);
else return querySum(sroot.left, i, mid) + querySum(sroot.right, mid+1, j);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []nums = new int[10];
for(int i=0;i<nums.length;++i) nums[i] = i;
SegmentTree st = new SegmentTree(0, nums.length-1, nums);
int tmp = querySum(st.root, 0, 9);
System.out.println(tmp);
st.updateByPoint(st.root, 5, 7);
System.out.println(querySum(st.root, 0, 9));
st.updateBySegment(st.root, 3, 4, 2);
System.out.println(querySum(st.root, 2, 7));
}
}
SegmentTree.java