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

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);
}

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);
}

6.Test

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));
    }
}

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));
    }
}