[LeetCode]307. Range Sum Query – Mutable

Solution

Use “Binary Indexed Tree (BIT)” (Fenwick Tree) data structure which supports querying prefix sum and adding a value to a single point.

Binary Indexed Tree is a data structure not introduced on most undergraduate and graduate algorithm classes. I would recommend a youtube here.

If you are not fully understand this data structure, don’t worry, just heed that:

  • c[] array starts from index 1.
  • add(int x, int y) means add x to position y.

Then, try to memorize “add()”, “sum()” and “low_bit()” operations code, they are short! Practice more and you will be more perfect with BIT!

Back to this leetcode question, one thing to pay attention is, in the question, update(1, 2) means update the value on index 1 to 2, not add 2 to index 1. So, don’t forget to update original array as well as to update c[] arryay.

public void update(int i, int val) {
    add(i + 1, val - nums[i]);
    nums[i] = val; //don't forget this step!
}

Code

class NumArray {
    private int N;
    private int c[];
    private int[] nums;
    public NumArray(int[] nums) {
        N = nums.length;
        c = new int[N + 1];
        this.nums = nums;
        for(int i = 1; i <= N; i++) {
            add(i, nums[i-1]);
        }
    }
    
    public void update(int i, int val) {
        add(i + 1, val - nums[i]);
        nums[i] = val; //don't forget this step!
    }
    
    public int sumRange(int i, int j) {
        return sum(j+1) - sum(i);
    }
    
    private void add(int x, int y) {
        while (x <= N) {
            c[x] += y;
            x += low_bit(x);
        }
    }
    
    private int sum(int x) {
        int ans = 0;
        while (x > 0) {
            ans += c[x];
            x -= low_bit(x);
        }
        return ans;
    }
    
    private int low_bit(int x) {
        return x & -x;
    }
}

Runtime: 8 ms, faster than 99.88% of Java online submissions for Range Sum Query – Mutable.Memory Usage: 45.4 MB, less than 93.75% of Java online submissions for Range Sum Query – Mutable.

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *