1. Description

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.

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.

2. Runtime Distribution

3. Submission Details

4. Example

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

private int[] tree;
private int[] nums;

public NumArray(int[] nums) {

	this.nums = nums;
	tree = new int[nums.length + 1];
	for (int i = 0; i < nums.length; i++) {
		add(i + 1, nums[i]);
	}
}

public void update(int i, int val) {
	add(i + 1, val - nums[i]);
	nums[i] = val;
}

public int sumRange(int i, int j) {
	return sum(j + 1) - sum(i);
}

private void add(int i, int val) {
	while (i < tree.length) {
		tree[i] += val;
		i += lowBit(i);
	}
}

private int sum(int i) {
	int result = 0;
	while (i > 0) {
		result += tree[i];
		i -= lowBit(i);
	}
	return result;
}

private int lowBit(int x) {
	return x & (-x);
}

[/restab]
[restab title="Java"]

static class Tree{
	int left;
	int right;
	int sum;
}

private Tree[] tree;
private int nums[];

public NumArray(int[] nums) {
    if(nums == null || nums.length == 0){
    	return;
    }
	this.nums = nums;
	tree = new Tree[nums.length * 4];
	for(int i = 0; i< tree.length ; i++){
		tree[i] = new Tree();
	}
	buildTree(1, nums.length, 1);
	for(int i = 0; i < nums.length; i++){
		updateTree(i + 1, nums[i], 1);
	}
}

public void update(int i, int val) {
	if(nums.length == 0){
		return;
	}
	int diff = val - nums[i];
	nums[i] = val;
	updateTree(i + 1, diff, 1);
}

public int sumRange(int i, int j) {
	if(nums.length == 0){
		return 0;
	}
	return sum(i + 1, j + 1, 1); 
}


private void buildTree(int l, int r, int index){
	
	tree[index].left = l;
	tree[index].right = r;
	if(l == r){
		return;
	}
	int mid = l + ((r - l) >> 1);
	buildTree(l, mid, index << 1);
	buildTree(mid + 1, r, index << 1|1);
}

private void updateTree(int pos, int val, int index){
	if(pos == tree[index].left && tree[index].left == tree[index].right){
		tree[index].sum += val;
		return;
	}
	tree[index].sum += val;
	int mid = tree[index].left +((tree[index].right - tree[index].left) >> 1);
	if(pos <= mid){
		updateTree(pos, val, index << 1);
	}else{
		updateTree(pos, val, index << 1 | 1);
	}
}

private int sum(int l, int r, int index){
	if(l == tree[index].left && r == tree[index].right){
		return tree[index].sum;
	}
	if(tree[index].left == tree[index].right){
		return 0;
	}
	
	int mid = tree[index].left +((tree[index].right - tree[index].left) >> 1);
	
	if(r <= mid){
		return sum(l, r, index << 1);
	}else if(l > mid){
		return sum(l, r, index << 1 | 1);
	}
	return sum(l, mid, index << 1) + sum(mid + 1, r, index << 1 | 1);
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode307 {

	private int[] tree;
	private int[] nums;

	public LeetCode307(int[] nums) {

		this.nums = nums;
		tree = new int[nums.length + 1];
		for (int i = 0; i < nums.length; i++) {
			add(i + 1, nums[i]);
		}
	}

	public void update(int i, int val) {
		add(i + 1, val - nums[i]);
		nums[i] = val;
	}

	public int sumRange(int i, int j) {
		return sum(j + 1) - sum(i);
	}

	private void add(int i, int val) {
		while (i < tree.length) {
			tree[i] += val;
			i += lowBit(i);
		}
	}

	private int sum(int i) {
		int result = 0;
		while (i > 0) {
			result += tree[i];
			i -= lowBit(i);
		}
		return result;
	}

	private int lowBit(int x) {
		return x & (-x);
	}

	public static void main(String[] args) {
		int[] nums = new int[] { 1, 3, 5 };
		LeetCode307 leetcode = new LeetCode307(nums);
		System.out.println(leetcode.sumRange(0, 2));
		leetcode.update(1, 2);
		System.out.println(leetcode.sumRange(0, 2));
	}
}

[/restab]
[restab title="Java"]

public class LeetCode0307_1 {

	static class Tree{
		int left;
		int right;
		int sum;
	}
	
	private Tree[] tree;
	private int nums[];

	public LeetCode0307_1(int[] nums) {
        if(nums == null || nums.length == 0){
        	return;
        }
		this.nums = nums;
		tree = new Tree[nums.length * 4];
		for(int i = 0; i< tree.length ; i++){
			tree[i] = new Tree();
		}
		buildTree(1, nums.length, 1);
		for(int i = 0; i < nums.length; i++){
			updateTree(i + 1, nums[i], 1);
		}
	}

	public void update(int i, int val) {
		if(nums.length == 0){
			return;
		}
		int diff = val - nums[i];
		nums[i] = val;
		updateTree(i + 1, diff, 1);
	}

	public int sumRange(int i, int j) {
		if(nums.length == 0){
			return 0;
		}
		return sum(i + 1, j + 1, 1); 
	}
	
	
	private void buildTree(int l, int r, int index){
		
		tree[index].left = l;
		tree[index].right = r;
		if(l == r){
			return;
		}
		int mid = l + ((r - l) >> 1);
		buildTree(l, mid, index << 1);
		buildTree(mid + 1, r, index << 1|1);
	}
	
	private void updateTree(int pos, int val, int index){
		if(pos == tree[index].left && tree[index].left == tree[index].right){
			tree[index].sum += val;
			return;
		}
		tree[index].sum += val;
		int mid = tree[index].left +((tree[index].right - tree[index].left) >> 1);
		if(pos <= mid){
			updateTree(pos, val, index << 1);
		}else{
			updateTree(pos, val, index << 1 | 1);
		}
	}
	
	private int sum(int l, int r, int index){
		if(l == tree[index].left && r == tree[index].right){
			return tree[index].sum;
		}
		if(tree[index].left == tree[index].right){
			return 0;
		}
		
		int mid = tree[index].left +((tree[index].right - tree[index].left) >> 1);
		
		if(r <= mid){
			return sum(l, r, index << 1);
		}else if(l > mid){
			return sum(l, r, index << 1 | 1);
		}
		return sum(l, mid, index << 1) + sum(mid + 1, r, index << 1 | 1);
	}
	
	public static void main(String[] args) {
		int[] nums = new int[] { 1, 3, 5 };
		LeetCode0307_1 leetcode = new LeetCode0307_1(nums);
		System.out.println(leetcode.sumRange(0, 2));
		leetcode.update(1, 2);
		System.out.println(leetcode.sumRange(0, 2));
	}
}

[/restab]
[/restabs]